perm filename V2K.IN[TEX,DEK] blob
sn#285516 filedate 1977-05-29 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00015 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 folio 465 galley 1
C00014 00003 folio 468 galley 2
C00037 00004 folio 473 galley 3
C00055 00005 folio 476 galley 4
C00068 00006 folio 479 galley 5 WARNING: Tape mostly unreadable, NEXT TEN GALLEYS.
C00080 00007 folio 482 galley 6
C00095 00008 folio 488 galley 7
C00112 00009 folio 492 galley 8
C00131 00010 folio 496 galley 9
C00147 00011 folio 500 galley 10
C00163 00012 folio 505 galley 11
C00178 00013 folio 508 galley 12
C00196 00014 folio 512 galley 13
C00211 00015 folio 515 galley 14
C00224 ENDMK
C⊗;
folio 465 galley 1
0 {U0}{H10L12M29}|πW58320#Computer Programming!ch.
2 4!f. 465!g. 1|'{A6}of ln|4|εX|βn |πis, to a very
11 good approximation,|'{A6}|ε|(|π1|d2ln|42|)|4|↔j|ur1|)0|)|4|(
13 |πln|4|εx|d21|4α+↓|4x|)|4dx|4|∂α=↓|4α_↓|4|(|π1|d2ln|42|)|4|↔
13 j|ur|¬1|)0|)|4|(|εue|gα_↓|gu|d21|4α+↓|4e|gα_↓|gu|)|4du|'
14 {A4}|Lα=↓|4α_↓|4|(|π1|d2ln|42|)|4|↔k|uc|)|εk|1|1|¬¬C5|11|)|4
14 (|→α_↓1)|gk|gα+↓|g1|4|↔j|ur|¬1|)0|)|4ue|gα_↓|gk|gu|4du>
15 {A4}|Lα=↓|4α_↓|4|(|π1|d2ln|42|)|4(1|4α_↓|4|f1|d34|)|4α+↓|4|f
15 1|d39|)|4α_↓|4|f1|d316|)|4α+↓|4|f1|d325|)|4α_↓|4αo↓|4αo↓|4αo
15 ↓)>{A4}|Lα=↓|4α_↓|4|(|π1|d2ln|42|)|4(1|4α+↓|4|f1|d34|)|4α+↓|
16 4|f1|d39|)|4α+↓|4αo↓|4αo↓|4αo↓|4α_↓|42(|f1|d34|)|4α+↓|4|f1|d
16 316|)|4α+↓|4|f1|d336|)|4α+↓|4αo↓|4αo↓|4αo↓)|≥2>
17 {A4}|Lα=↓|4α_↓|4|(|π1|d22|4ln|42|)|4(1|4α+↓|4|f1|d34|)|4α+↓|
17 4|f1|d39|)|4α+↓|4αo↓|4αo↓|4αo↓)>{A4}|Lα=↓|4α_↓|ε|≤p|g2/12|4|
18 πln|42.#>{A6}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
19 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
19 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
19 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
19 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
19 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
19 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
19 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
19 }}}}}}|[π|πTherefore by (48) we expect to have
26 the approximate formula|'{A6}|ε|→α_↓t|≤p|g2/(12|4|πln|42)|4|
29 ¬V|4|→α_↓ln|4|εN;|;{A6}|πthat is, |εt |πshould
34 be approximately proportional to (12|4ln|4|ε2/|≤p|g2)|4|πln|
38 4|εN. |πThis constant (12|4ln|4|ε2/|≤p|g2)|4α=↓|40.842765913
41 |4.|4.|4. |πagrees perfectly with the empirical
47 formula (47) obtained earlier, so we have good
55 reason to believe that the formula|'{A6}|ε|≤t|βn|4|¬V|4|(|π1
61 2|4ln|42|d2|ε|≤p|g2|)|4|πln|4|εn|4α+↓|41.47|J!(51)|;
62 {A6}|πindicates the true asymptotic behavior
67 of |ε|≤t|βn |πas |εn|4|¬M|4|¬X.|'|π!|9|4|1|1|1If
72 we assume that (51) is valid, we obtain the formula|'
82 {A6|εT|βnN4|¬V|4←(*4π3264⊂n|426d2|ε*3*2*2|g2|)←↔a|πln|4|εn|4α_↓|
82 4|↔k|uc|)dF1|¬D|1,N)←4←*/*3≤<|\(-)≡≠F↔?S4α~↓*441.67,]J!(52)*4;{A
82 6}|πwqeje |*/|≤8|\|ε(-)?|πiss|ε#on Mangoldt's
85 function |πde_ned by the rules|'{A6}|ε|*/*/≤8|\(↔)←4α=↓|4|↔A|(
90 |πln|4|εp,$!|πifs|εn|4α≡↓**4∀|gr |π↔brn|εp *4π#rime,$!|εr|4|¬R
92 |41;|d5←πotherwise.|)|JD(53)|;{A2}|π'FbrcsxjxpleS'↓J*/}|ε⊗T|β
93 1←β0←β0←44∪4¬}C44(*4[3364⊂cN466f↑6≥\*2*2Ig26)*4↔a|π⊂nN4100|4α_↓|
93 4|(ln|42|d22|)|4α_↓|4|(⊂n|42|d26←)|4α_↓←4|(lnN45←d25←)|4α_↓|
93 4|(ln|45|d225|)|↔s|4α+↓|41.47!|;{A4}|PP}}V4(.*4*/7*2(**.6π554≠↓|
94 40.347|4α_↓|40.173←4α_↓|40.322|4α_↓|40.064)|4α+↓*441.47>
95 {A4e|LI¬}C44.59;%↓J**}|πthesexjcg v¬wqusmxf|\*5HI14I1→I1→|[/us
96 4777#[,'Offcvkjse weshavesnoo yez |ε∀rovddf|[≠kxzhicvvu∧bkq
100 |≥*5|icn|[≠kff|ε&|≤~|βnn|π∪n gendjal; so far we
105 have onlysbeen consideringcplausiblesrdaubmfswyyshhssa∧bvjsf
107 xrvkqausok¬vhhhomhmg∧).FXggukkwewqsit issno∧upvxsu∧∧estomsuq
108 plqsccvgrg¬uspcgoxf↔,x∧usdfmmnuuckjjfkqpukkwqyuusxxyss¬¬jjwp
108 m¬whyx¬wpccukf)[,'!|9*344555551Hyspwajkcvvcvb∃*2cufmh)3645vnI6
108 *26\≥*2pVg6 [7cn hhsu∧bv¬snfocmulas was established
113 _rst, in independdfo studkussbxsJ∧mnnF),Fk¬bnnukffHakfsA*2,He
116 ul∧jgnn.,Dk¬bnn[[≥↑*2 NuxxbjcThebg¬s|π]≡**/(*57(,
118 i41*?*?*?*?ixon [|εJ. Number Theory |π|≡2 (1970),
124 414<422] developed the theory of the |εF|βn(x)
131 |πdistributions to show that individual partial
137 quotients are essentially independent of each
143 other in an appropriate sense, and proved that
151 for all positive |ε|≤o |πwe have |¬G|εT(m,|4n)|4α_↓|4|≥1(12|
157 4|πln|42)/|ε|≤p|g2)|4|πln|4|εn|¬G|4|¬W|4(|πln|4|εn)|g(|g1|g/
157 |g2|g)|gα+↓|g|≤o |πexcept for exp(|ε|→α_↓c(|≤o)(|πlog|4|εN)|
160 g|≤o|g/|g2)N|g2 |πvalues of |εm, n |πin the range
168 |ε1|4|¬E|4m|4|¬W|4n|4|¬E|4N, |πwhere |εc(|≤o)|4Q|40.
171 |πHeilbronn's approach was completely di=erent,
176 working entirely with integers instead of continuous
183 variables. His idea, which is prjsented in slightly
191 modi_ed form in exercises 33 and 34, is based
200 on the fact that |ε|≤t|βn |πcan be related to
209 the number of ways to represent |εn |πin a certain
219 manner. Furthermore, his paper [|εNumber Theory
225 and Analysis, |πed. by Paul Tur|=1an (New York:
233 Plenum, 1969), 87<96] shows that the distribution
240 of individual partial quotients 1, 2,|4.|4.|4.
246 which we have discussed above actually applies
253 to the entire collection of partial quotients
260 belonging to the fractions havicvvuugivenndenominator;
265 this is a sharper form of Theorem E. A still
275 sharper result was obtained several years later
282 by J. W. Porter |ε[Mathematika |π|≡2|≡2 (1975),
289 20<28], who established that |ε|≤t|βn|4α=↓|4|≥1(12|4|πln|42)
293 /|ε|≤p|g2)|4|πln|4|εn|4α+↓|4C|4α+↓|4O(n|gα_↓|g1|g/|g6|gα+↓|g
293 |≤o|≥2, |πwhere |εC|4α=↓|41.4670780794|4.|4.|4.
296 |πcan be expressed as a complicated combination
303 of sums and integrals. Thus the conjecture (47)
311 is fully proved.|'{A6}!|9|4|1|1|1We can also
317 estimawte the9|4|1|1|1We can also estimate the
323 average number of division steps when |εu |πand
331 |εv |πare both uniformly distributed between
337 1 and |εN, |πby calculating|'{A6}|(|ε1|d2N|)|4|↔k|uc|)1|¬En|
342 ¬EN|)|4T|βn.|J!(54)|;{A6}|πAssuming formula (52),
346 this sum has the form|'{A6}|(|π12|4ln|42|d2|ε|≤p|g2|)|4|πln|
351 4|εN|4α+↓|4O(1),|J!(55)|;{A6}|π(see exercise
354 27), and empirical calculations with the same
361 numbers used to derive Eq. 4.5.2<45 show good
369 agreement with the formula|'{A6}|ε|(|π12|4ln|42|d↑6ε|≤p|g2|)
373 |4|πln|4|εN|4α+↓|40.06.|J!(56)|;{A6}!|9|4|1|1|1|πThe
375 average running time for Euclid's algorithm on
382 multiprecision integers, using classical algorithms
387 for arithmetic, was shown to be of order |≥11|4α+↓|4log(max(
395 |εu,|4v)/|πgcd(|εu,|4v)|≥2|≥2|1|1|πlog|4min(|εu,|4v)
396 |πby G. E. Collins, |εSIAM J. Computing |π|≡3
404 (1974), 1<10.|'|'|≡*3|≡u|≡m|≡m|≡a|≡r|≡y|≡.|9|4We
408 have found that the worst case of Euclid's algorithm
417 occurs when its inputs |εu and |εv |πare consecutive
426 Fibonacci numbers (Theorem F); the number of
433 division steps when |εv|4α=↓|4n |πwill never
folio 468 galley 2
439 exceed |"p4.8|4log|β1|β0|4|εN|4α_↓|40.32|"P.
441 |πWe have determined the freqqufcy of the values
449 of various partial quotients, showing, for example,
456 that the division step _nds |"l|εu/v|"L|4α=↓|41
462 |πabout 41 percent of the time (Theorem E). And,
471 _nally, the theorems of Heilbronn and Dixon show
479 that the average number |εT|βn |πof division
486 steps when |εv|4α=↓|4n |πis approximately|'{A6}|π(12|4{U0}{H
491 10L12M29}|πW58320#Computer Programming!ch. 4!f.
494 468!g. 2|'{A6}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'|'
498 {H9L11}|9|1|≡1|≡.|9|4[|*/|↔P|↔c|\]|9|πSince the
500 quotient |ε|"lu/v|"L |πis equal to unity over
507 40 percent of the time, it may be advantageous
516 on some computers to make a test for this case
526 and to avoid the division when the quotient is
535 unity. Is the following |¬m|¬i|¬x program for
542 Euclid's algorithm more e∃cient than Program
548 4.5.2A?|'{A6}|h|∂|9|1|1|9|1|1!|∂|9|1|1|9|1|1|9|1|1|9|1|1!|∂|
549 9|1|1|9|1|1!!|∂|εrX|4|¬L|4rAX|4|πmod|4|εv.|9|E|n|;
550 |L|L|π|¬l|¬d|¬x|L|¬u|LrX|4|¬L|4|εu.>|L|L|π|¬j|¬m|¬p|L|¬2|¬f|
551 L>|L|¬1|¬h|L|¬s|¬t|¬x|L|¬v|L|εv|4|¬L|4|πrX.>|L|L|¬s|¬u|¬b|L|
553 ¬v|LrA|4|¬L|4|εu|4α_↓|4v.>|L|L|π|¬c|¬m|¬p|¬a|L|¬v>
555 |L|L|¬s|¬r|¬a|¬x|L|¬5|LrAX|4|¬L|4rA.>|L|L|¬j|¬l|L|¬2|¬F|LIs|
556 4|εu|4α_↓|4v|4|¬W|4v?>|L|L|π|¬d|¬i|¬v|L|¬v|LrX|4|¬L|4rAX|4mo
557 d|4|εv.>|L|π|¬2|¬h|L|¬l|¬d|¬a|L|¬v|LrA|4|¬L|4|εv.>
559 |L|L|π|¬j|¬x|¬n|¬z|L|¬1|¬b|LDone if rX|4α=↓|40.>
562 {A6}|9|1|≡2|≡.←9|4[|εM|*/|↔P|↔O|\]|9|πEvaluate
563 the matrix product|'{A6}|↔a|(|εx|β1|d51|)!|(1|d50|)|↔s|↔a|(x
566 |β2|d51|)!|(1|d50|)|↔s|4αo↓|4αo↓|4αo↓|4|↔a|(x|βn|d51|)!|(1|d
566 50|)|↔s.|;{A6}|π|9|1|≡3|≡.|9|4[|εM|↔P|↔O]|9|πWhat
568 is the value of|'{A6}|ε|h|∂|πdet!|4|∂|→α_↓1$|∂|→α_↓1!|∂|→α_↓
572 1!|∂←→α_↓1!|∂0!|9|∂|E|n|;|>|;|9|4|εx|β1|'|9|41|'
577 |9|40|'αo↓|4αo↓|4αo↓|'0|'>{A2}|>|'|→α_↓1|'|9|4xSβ2|'
585 |9|41|'|'0|'>{A2}|>|'|9|40|'|→α_↓1|'|9|4x|β3|'
594 |9|41|'|1|1αo↓|'>|>|πdet|'|'|'|'|'|1|1αo↓|'>|>
606 |'|'|'←→α_↓1|'|'|1|1αo↓|'>|>|'|'|'←'←'1|'>{A2}|>
620 |'|9|40|'|9|40|'.|4.|4.←'|→α_↓1←'|εx|β,|'>{A6}|9|1|π|≡5|≡.|9
625 |4[|εHM|*/|↔P|↔C|\]|9|πLet |εx|β1, x|β2,|4.|4.←4.
628 |πbe a sequefce ofsreal numberf which are each
636 greater than some positive real number |ε|≤e)
643 |πProve that the in_nite continued fraction |"C|εx|β1,|4x|β2
649 ,|4.|4.|4.|"C|4α=↓|4|πlim|ε|βn|1|β|¬XN1←β|¬XF1|1|"CxFβ1,←4.]
649 4#]4.|4,]4)|βn|"6 |πexists. Show also that |"C|εx|β1,|4x|β2,
654 |4.|4.|4.|"C |πneed not exist if we assume only
662 that |εx|βj|4|¬Q|40 |πfor all |εj.|'{A3}|9|1|π|≡6|≡.|9|4[|εM
667 |*/|↔P|↔L|\]|9|πProve that the regular continued
672 fraction expansion expansion of a nuxber is |εunique
680 |πin the following sense: If |εB|β1, B|β2,|4.|4.|4.
687 |πare positive integers,λthen thesin_nitescontinued
691 frjkoion |"CNεB|β1,]4B|β2,|4.|4.|4.|"C |πis an
695 irrational number |εX |πbetweef 0 andn1λwhofe
701 rd∧kwar conoinuedffkjction has |εA|βn|4α=↓|4B|βn
705 |πfor all |εn|4|¬R|41; |πand if |εB|β1,|4.|4.|4.|4,|4B|βm
711 |πare positive integers with |εB|βm|4|¬Q|41,
716 |πthen the regular continued fjaction forn|εXN4(*244.7}Xi1,N4
721 #.47.4#[4/]4XivM.6c|π.aus|≥%UβcN4≡↓*44αFicn|π↔brc|≥*544←¬DS4/N
721 44¬DS4#.M,{{3}o|9|1|≡7|≡.]9:4[[N*/←↔P|↔o|\]|9|π*4indsall
722 pqjv¬qazionfs|εp(1)*45∀(2)←4.N4.N4#[4∀(n) |πof
724 |¬T1,|42,|4.]4.|4.←4,|4|εn|¬Y |πsuch that |εQ|βn(x|β1,]4x|β2
727 ,←4.]4#]4.|4,]4*2Sβn)*44α≡↓|4\Sβn()|βp|β(|β1←β),
728 x|βp|β(Nβ2|β),|4.←4.]4.←4,λxFβp|β(|βn|β)) |πholds
730 for awl |εxFβ1,λx|β2,←4.]4.|4.|4,|4x|βn.|'{A3}|:*35←≡8*3≡)]9*34
733 [[N*/*3↔5|↔≡C\]|9*3πIf |εXSβn |π∪ssde_ned↔λin the
737 re∧ular continued fraction process, show that
743 |"C|εA|βn,|4.|4.|4.|4,←4A|β1,λ|→α_↓X|"6|4α=↓|4|→α_↓1/X|βn.|'
744 {A3}|9|14≡α|≡)[::4⊗[NεN*/*3↔\|*4αN\**]9*3π*4yo∧sthaw
745 cvnmickudffkjkgignfssazisfysthe following identities:|'
748 !!|5←1_*2*4::55[7C\*2Xi1#]4#[47[4#[4,]4XIcN.6C4*2↓←4←.7¬Fβ1,]4#[
748 4#]4#[4/]4XikF4α~↓**44"6¬XIkKi↓~↓β1,]4#[4.[4#[4/]4)|βnN"6|"C,
748 !!1|4|¬E|4k|4|¬E|4n;|'!!|1414πα)(::.7C≥*5,]4*2Xi1#]4*2Fβ2/]4#[4
749 #[4#]4/]4*2SβnN"6|4α=↓|4)Fβ1←4α+↓|4←"6xFβ2/]47[4#[4#]4/]4*2Xic
749 N.76]!NN44}}C45\:]'!!|5555[/*2(::5555\\[7}XI1#]47[47[47[46]4X
749 IkKI↓↓↓I17]4XIk≡]45[]4*2XikKI↓α↓i17]4XikKi↓~↓I26]47[4#[4#[4/]
749 4XIcN"6C]'|[7}XI17]47[47[47[46]44xXIkKi↓≠↓**β1/]4XIkF4~↓4)Nβk
749 KI↓~↓*4β1/]4*2FβkKi↓~↓**β2,]4#]4#]47[4/]4*2FicN[76]!1544}}C4**K44
749 }}Q46):*3?!!|5514π-)*49:\*544α≠↓**44.6¬Sβ16]4*2Fβ2,]4.]4.←4.]4/]4
749 )SβcN[7C4≡**44[777]4XI154≤↓457]4XI26]47[4#[4#[46]4XIcN.7/]!nN
749 4←¬}C45#],{A↓}|[]**5≡→***2[::47]≥M*/*/↔I↔≤I\]:*3[αxsthesrjsuwl
750 mffsxdjccses6,λe¬jj¬sirrjwionjwpcjawink¬xbjc|≥X|[[qusuuukcqq
750 uscj∧¬qwjccvmmpckudffkjkction represent*?*?*?continued
752 fraction representation of the form|'{A6}|εX|4α=↓|4A|β0|4α+↓
757 |4|"CA|β1,|4A|β2,|4A|β3,|4.|4.|4.|"C,|;{A6}|πwhere
759 |εA|β0 |πis an integer and |εA|β1, A|β2, A|β3,|4.|4.|4.
767 |πare positive integers. Show that if |εX |πhas
775 this representation then the regular continued
781 fraction for |ε1/X |πis|'{A6}|ε1/X|4α=↓|4B|β0|4α+↓|4|"CB|β1,
785 |4.|4.|4.|4,|4B|βm,|4A|β5,|4A|β6,|4.|4.|4.|"C|;
786 {A6}|πfor suitable integers |εB|β0, B|β1,|4.|4.|4.|4,
791 B|βm. |π(This case |εA|β0|4|¬W|40 |πis of course
798 the most interesting.) Explain how to determine
805 the |εB'|πs in terms of |εA|β0, A|β1, A|β2, A|β3,
814 |πand |εA|β4.|'{A3}|≡1|≡1|≡.|9|1[M|*/|↔L|↔c|\]|9|π(J.
817 Lagrange.))PWt |εX|4α=↓|4A|β0|4α+↓|4|"CA|β1,|4A|β2,|4.|4.|4.
818 |"C, Y|4α=↓|4B|β0|4α+↓|4|"CB|β1,|4B|β2,|4.|4.|4.|"C
820 |πbe the regular continued fraction representations
826 of two real numbers |εX |πand |εY, |πin the sense
836 of exercise 10. Show that these representations
843 ``eventually agree,'' in the sense that |εA|βm|βα+↓|βk|4α=↓|
849 4B|βn|βα+↓|βk |πfor some |εm |πand |εn |πand
856 for all |εk|4|¬R|40, |πif and only if |εX|4α=↓|4(qY|4α+↓|4r)
863 /(sY|4α+↓|4t) |πfor some integers |εq, r, s,
870 t |πwith |ε|¬Gqt|4α_↓|4rs|¬G|4α=↓|41. |π(This
874 theorem is the analog, for continued fraction
881 representations, of the simple result that the
888 representations of |εX |πand |εY |πin the decimal
896 system eventually agree if and only if |εX|4α=↓|4(10|gqY|4α+
903 ↓|4r)/10|gs |πfor some integers |εq, r, |π≠fd
910 |εs.)|'{A3}|ε|≡1|≡2|≡.|9|4[M|*/|↔L|↔c|\]|9|πA
912 |εquadratic irrationality |πis a number of the
919 form (|ε|¬H|v4D|)|4α_↓|4U)/V, |πwhere |εD, U,
924 |πand |εV |πare integers, |εD|4|¬Q|40, V|4|=|↔6α=↓|40,
930 |π_fds|εD |πis noo a perfeco square. We may assume
939 without loss of generality that |εV |πis a divisor
948 of |εD|4α_↓|4U|g2, |πfor otherwise the number
954 may be rewritten as (|}¬H|v*?*?e nkmber may be
962 rewritten as (|¬H|v4|εDV{J.5}|g2|)|4α_↓|4U|1|1|¬GV|¬G)/V|1|1
964 |¬GV|¬G.|'!!|1|1|πa)|9Prove that the regular
969 continued fraction expansion (in the sense of
976 exercise 10) of a quadratic irrationality |εX|4α=↓|4(|¬H|v4D
982 |)|4α_↓|4U)/V |πis obtained by the following
988 formulas:|'{A6}|εV|β0|4α=↓|4V,!!A|β0|4α=↓|4|"lX|"L,!!U|β0|4α
989 =↓|4U|4α+↓|4A|β0V;|;V|βn|βα+↓|β1|4α=↓|4(D|4α_↓|4U|1|=|βn|g2)
990 /V|βn,!!A|βn|βα+↓|β1|4α=↓|4|"l(|¬H|v2D|)|4α+↓|4U|βn)/V|βn|βα
990 +↓|β1|"L,|;{A4}U|βn|βα+↓|β1|4α=4*/|βn|βα+↓|β1V|βn|βα+↓|β1|4α_
991 ↓|4U|βn.|;{A6}|π[|εNote|*/:|\ |πAn algorithm based
996 on this process has many applications to the
1004 solution of quadratic equations in integers;
1010 see, for example, H. Davenport, |εThe higher
1017 arithmetic (|πLondon: Hutchinson, 1952); W. J.
1023 LeVeque, |εTopics in Number Theory (|πReading,
1029 Mass.: Addison-Wesley, 1956); and see Section
1035 4.5.4. By exercise 1.2.4<35, |εA|βn|βα+↓|β1|4α=↓|4|"l(|"l|¬H
1039 |v4D|)|1|"L|4α+↓|4U|βn)/V|βn|βα+↓|β1|"L |πwhen
1041 |εV|βn|βα+↓|β1|4|¬Q|40, |πand |εA|βn|βα+↓|β1|4α=↓|4|"l(|"l|¬
1043 H|v4D|)|"L|4α+↓|41|4α+↓|4U|βn)/V|βn|βα+↓|β1|"L
1044 |πwhen |εV|βn|βα+↓|β1|4|¬W|40; |πhence such an
1049 algorithm need only work qqph the integer |"l|ε|¬H|v4D|)|1|"
1056 L.]|'|π!!|1|1b)|9Prove that |ε0|4|¬W|4U|βn|4|¬W|4|¬H|v4D|)|1
1059 , 0|4|¬W|4V|βn|4|¬W|42|¬H|v4D|)|1, |πfor all
1063 |εn|4|¬Q|4N, |πwhere |εN |πis some integer depending
1070 on |εX; |πhence the regular continued fraction
1077 representation of every quadratic irrationality
1082 is eventually periodic. [|εHint|*/:|\ |πShow that
1088 (|→α_↓|ε|¬H|v4D|)|4α_↓|4U)/V|4α=↓|4A|β0|4α+↓|4|"CA|β1,|4.|4.
1088 |4.|4,|4A|βn, |→α_↓V|βn/(|¬H|v4D|)|4α+↓|4U|βn)|"C,
1090 |πand use Eq. (5) to prove that (|ε|¬H|v4D|)|4α+↓|4U|βn)/V|β
1097 n |πis positive when |εn |πis large.]|'!!|1|1c)|9|1|1Letting
1104 |εp|βn|4α=↓|4Q|βn|βα+↓|β1(A|β0,|4A|β1,|4.|4.|4.|4,|4A|βn)
1106 |πand |εq|βn(A|β1,|4.|4.|4.|4,|4A|βn), |πprove
1109 that |εVp|=|βn|g2|4α+↓|42Up|βnq|βn|4α+↓|4|≥1(U|g2|4α_↓|4D)/V
1110 |1)q|=|βn|g2|4α=↓|4(|→α_↓1)|gn|gα+↓|g1V|βn|βα+↓|β1.|'
1111 !!|1|1|πd)|9PVrove hqz thesrdgular continued
1115 fraction representation of an irrational number
1121 |εX |πis eveftually periodic if and only if |εX
1130 |πis a quadratic irrationality. (This is the
1137 continued fraction analog of the fact that the
1145 decimal expansion of a real number |εX |πis eventually
1154 periodicnif afdfongqsif |ε(f|πcs rjwionjl#)(,{J3d|≡1←≡3←≡.]9
1157 *3ε[M|*/|↔M|↔c|\*4]9(*3πJ.λLagrange, 1797.)↔Let |εf(x)|4α=↓|4a|β
1159 nx|gn|4α+↓|4αo↓|4αo↓|4α↓|4α+↓|4a|β0,|4a|βn|4|¬Q|40,
1160 |πbe a polynomial with integer coe∃cients, having
1167 no rational roots, and having exactly one real
1175 root |ε|≤j|4|¬Q|41. |πDesign a computer program
1181 to _nd the _rst thousand or so partial quotientssnof
1190 ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1192 |||||||||||||||||||||||||||||||||||||||||||||||||||||||*?*?enm
1192 ysof |ε|≤j, |πusing the following algorithm (which
1199 involves only multiprecision addition).|'{A6}{I1.6H}|≡L|≡1|≡
1203 .|9Set |εA|4|¬L|41.|'|π|≡L|≡2|≡.|9For |εk|4α=↓|40,|41,|4.|4.
1206 |4.|4,|4n|4α_↓|41 (|πin this order), and for
1212 |≥≤|4α=↓|4n|4α_↓|41,|4.|4.|4.|4,|4k |π(in this
1215 order) set |εa|βj|4|¬L|4a|βj|βα+↓|β1|4α+↓|4a|βj.
1218 |π(This step replaces |εf(x) |πby |εg(x)|4α=↓|4f(x|4α+↓|41),
1223 |πa polynomial whose roots are one less than
1232 those of |εf.)|'{A3}|π|≡L|≡3|≡.|9If |εa|βn|4α+↓|4a|βn|βα_↓|β
1236 1|4α↓|4αo↓|4αo↓|4αo↓|4α+↓|4a|β0|4|¬W|40, |πset
1238 |εA|4|¬L|4A|4α+↓|41 |πand return to L2.|'{A3}|≡L|≡4|≡.|9Outp
1243 ut |εA (|πwhich is the value of the next partial
1253 quotient). Replace (|εa|βn,|4a|βn|βα_↓|β1,|4.|4.|4.|4,|4a|β0
1255 ) |πby |ε(|→α_↓a|β0,|4|→α_↓a|β1,|4.|4.|4.|4,|4|→α_↓a|βn)
1258 |πand return to L1. (This step replaces |εf(x)
1266 |πby a polynomial whose roots are reciprocals
1273 of those of |εf.)|'{A6}{IC}t|πFor example, starting
1280 with |εf(x)|4α=↓|4x|g3|4α_↓|42, |πthe algorithm
1284 will output 1 (changing |εf(x) |πto |εx|g3|4α_↓|43x|g2|4α_↓|
1290 43x|4α_↓|41); |πthen 3 (changing |εf(x) |πto
1296 |ε10x|g3|4α_↓|46x|g2|4α_↓|46x|4α_↓|41); |πetc.|'
1298 {A3}|≡14≡4←≡.←9*34←ε[MN*/←↔P|↔|\]|9←π(↑. Hurwutz,
1300 1891.) Showsthat the following rules make it
1307 possible to _nd the regular continued fraction
1314 expansion for |ε2X, |πgiven the partial quotientssof
1321 |εX:*3'↓J6}2|"C2a,|4b,|4c,|4.|4.|4.|"C|4α=↓|4|"Ca,←42b|4α+↓|4
1321 2|"Cc,|4.|4.←4.|"C|"C;|;{A4}2|"C2_|4α+↓|41,]4b,|4c,←4.←4.←4#
1322 ]"6|4α=↓|4←"6a,←41,|41|4α+↓|426|"CCCCCCCCCCCCCCCCCVC}C}C}C∧}
1322 b¬bbbbbbb*?*?*?"Ca↔|41,|41|4α+↓|42|"Cb|4α_↓|41,|4c,|4.|4.|4.|"C
1322 |"C.|;{A6}|πUse this idea to _nd the regular
1330 continued fraction expansion of |ε|f1|d32|)e,
1335 |πgiven the expansion of |εe |πin (13).|'{A3}|≡1|≡5|≡.|9|ε[M
1342 |*/|↔L|↔O|\]|9|π(R. W. Gospen.) Generalizing exercise
1347 14, design an algorithm which computes the continued
1355 fraction |εX|β0|4α+↓|4|"CX|β1,|4X|β2,|4.|4.|4.|"C
1357 |πfor |ε(ax|4α+↓|4b)/(cx|4α+↓|4d), |πgiven the
1361 continued fraction |εx|β0|4α+↓|4|"Cx|β1,|4x|β2,|4.|4.|4.|"C
1364 |πfor |εx, |πand given integers |εa, b, c, d
1373 |πwith |εad|4|=|↔6α=↓|4bc. |πMake your algorithm
1378 an ``on-line coroutine'' which outputs as many
1385 |εX|βk |πas possible before inputting each |εx|βj.
1392 |πDemonstrate how your algorithm computes |ε(97x|4α+↓|439)/(
1397 |→α_↓62x|4α_↓|425) |πwhen |εx|4α=↓|4|→α_↓1|4α+↓|4|"C5,|41,|4
1399 1,|41,|42,|41,|42|"C.|'{A3}|π|≡1|≡6|≡.|9|4|ε[HM|*/|↔L|↔c|\]|9
1400 (|ε|πL. Euler, 1731.) Let |εf|β0(z)|4α=↓|4(e|gz|4α_↓|4e|gα_↓
1404 |gz)/(e|gz|4α+↓|4e|gα_↓|gz)|4α=↓|4|π+anh|4|εz,
1405 |πand let |εf|βn|βα+↓|β1(z)|4α=↓|41/f|βn(z)|4α_↓|4(2n|4α+↓|4
1407 1)/z. |πProve that, for all |εn, f|βn(z) |πis
1415 an analytic function of the complex variable
1422 |εz |πin a neighborhood of the ogcgin, and it
1431 satis_es the di=erential equation |εf|1|=|βnαO↓(z)|4α=↓|41|4
1435 α_↓|4f|βn(z)|g2|4α_↓|42nf|βn(z)/z. |πUse this
1438 fact to prove that|'{A6}tanh|4|εz|4α=↓|4|"Cz|gα_↓|g1,|43z|gα
1442 _↓|g1,|45z|gα_↓|g1,|47z|gα_↓|g1,|4.|4.|4.|"C.|;
1443 {A6}|πThen apply Hujwitz's rule (exercise 14)
1449 to prove that|'{A6}|εe|gα_↓|g1|g/|gn|4α=↓←4←"C|v21,|4(2m|4α+
1452 ↓|41),|4α_↓|41,|41|)|"C,!!m|4|¬R|40.|;{A6}|π(This
1454 notation denotes the in_nite continued fraction
1460 |"C1,|4n|4α_↓|41,|41,|41,|43|εn|4α_↓|41,|41,|41,|45n|4α_↓|41
1460 ,|41,|4.|4.|4.|"C.) |πAlso _nd the regular continued
1466 fraction expansion for |εe|gα_↓|g2|g/|gn |πwhen
1471 |εn|4|¬Q|40 |πis odd.|'{A3}|≡1|≡7|≡.|9|4|ε[M|*/|↔P|↔L|\]|9(a)
1474 |πProve that |ε|"Cx|β1,|4|→α_↓x|β2|"C|4α=↓|4|"Cx|β1|4α_↓|41
1477 ,|41,|4x|β2|4α_↓|41|"C. |π(b) Generalize this
1481 identity, obtaining a formula for |ε|"Cx|β1,|4|→α_↓x|β2,
1487 x|β3, |→α_↓x|β4,|4.|4.|4.|4, x|β2|βn|βα_↓|β1,
1490 |→α_↓x|β2|βn|"C |πin which all partial quotients
1496 are positive integers when the |εx'|πs |πare
1503 large positive integers. (c) The result of exercise
1511 16 implies that tan|41|4α=↓|4|"C1,|4|→α_↓3,|45,|4|→α_↓7,|4.|
1514 4.|4.|"C. Find the regular continued fraction
1520 exp{U0}{H10L12M29}|πW58320#Computer Programming!ch.
folio 473 galley 3
1522 4!f. 473!g. 3|'{A6}{H9L11}|π|≡1|≡8|≡.|9|4|ε[M|*/|↔M|↔c|\]|9|π
1525 Develop a computer program to _nd as many partial
1534 quotients as possible of a real number given
1542 with high precision. Use this program to calculate
1550 the _rst one thousand (or so) partial quotients
1558 of Euler's constant |ε|≤g, |πbased on D. W. Sweeney's
1567 3566-place value |ε[Math. Comp. |π|≡1|≡7 (1963),
1573 170<178]. (Note that we expect to get about 0.97
1582 partial quotients per decimal digit. Cf. Algorithm
1589 4.5.2L and the article by J. W. Wrench, Jr. and
1599 D. Shanks, |εMath. Comp. |π|≡2|≡0 (1966), 444<447.)|'
1606 {A3}|≡1|≡9|≡.|9|4|ε[M|*/|↔P|↔c|\]|9|π7Vgve that
1608 |εF(x)|4α=↓|4|πlog|ε|βb(1|4α+↓|4x) |πsatis_es
1610 Eq. (24).N'{A3}|≡2|≡0|≡.|9|4|ε[HM|*/|↔P|↔c|\]|9|πDerive
1612 (36) from (35).|'{A3}|≡2|≡1|≡.|9|4|ε[HM|*/|↔P|↔m|\]|9(|πE.
1616 Wirsing.) The bounds (37) were obtained for a
1624 function |ε|≤' |πcorresponding to |εg |πwith
1630 |εTg(x)|4α=↓|41/(x|4α+↓|41). |πShow that the
1634 function which corresponds to |εTg(x)|4α=↓|41/(x|4α+↓|4c)
1639 |πyields better bounds, when |εc|4|¬Q|40 |πis
1645 an appropriate constant.|'{A3}|≡2|≡2|≡.|9|4[|εHM|*/|↔M|↔p|\]|
1648 9|π(E. Wirsing.) Find another term in the asymptotic
1656 expansion of |εF|βn(x), |πimproving on (38).|'
1662 {A3}|≡2|≡3|≡.|9|4|ε[HM|*/|↔P|↔L|\]|9|πProve (50),
1664 using results from the proof of Theorem W.|'{A3}|≡2|≡4|≡.|9|
1672 4|ε[M|*/|↔P|↔P|\]|9|πWhat is the average value
1677 of a partial quotient |εA|βn |πin the regular
1685 continued fraction expansion of a random real
1692 number?|'{A3}|≡2|≡5|≡.|9|4|ε[HM|*/|↔P|↔C|\*4]9←πFind
1694 an example of a set |ε|λi|4α=↓|4I|β1|4|↔q|4I|β2|4|↔q|4I|β3|4
1699 |↔q|4αo↓|4αo↓|4αo↓|4|↔Y|4[0,|41], |πwhere the
1702 |εi'|πs are disjocnt intervals, for which (42)
1709 does not hold.|'{A3}|≡2|≡6|≡.|9|4|ε[M|*/|↔P|↔L|\]|9|πShow
1713 that if the numbers |ε1/n, 2/n,|4.|4.|4.|4, |"ln/2|"L/n
1720 |πare expressed as regular continued fractions,
1726 the result is symmetric between left and right,
1734 in the sense that |"C|εA|βt,|4.|4.|4.|4,|4A|β2,|4A|β1|"C
1739 |πappears whenever |ε|"CA|β1,|4A|β2,|4.|4.|4.|4,|4A|βt|"C
1742 |πdoes.|'{A3}|≡2|≡7|≡.|9|4|ε[M|*/|↔P|↔O|\]|9|πDerive
1744 (52) from (46) and (51).|'{A3}|≡2|≡8|≡.|9|4|ε[M|*/|↔P|↔L|\]|9
1749 |πProve the following identities involving the
1755 three number-theoretical functions |ε|≤'(n),
1759 |≤m(n), |*/|≤!|\(n):|'|π!!|1|1a)|9|1|↔k|uc|)|εd|¬Dn|)|4|≤m(d)
1761 |4α=↓|4|≤d|βn|β1.!!!!|πb)|9ln|4|εn|4α=↓|4|↔k|uc|)d|¬Dn|)|4|*/
1761 |≤!|\(d),!!n|4α=↓|4|↔k|uc|)d|¬Dn|)|4|≤'(d).|'
1762 {A4}!!|1|1|πc)|9|1|1|ε|*/|≤!|\(n)|4α=↓|4|↔k|uc|)d|¬Dn|)|4|≤m|
1762 ↔a|(n|d2d|)|↔s|4|πln|4|εd,!!|≤'(n)|4α=↓|4|↔k|uc|)d|¬Dn|)|4|≤
1762 m|↔a|(n|d2d|)|↔s|1|1d.|'{A6}|π|≡2|≡9|≡.|9|4|ε[M|*/|↔P|↔L|\]|9
1763 |πAssuming that |εT|βn |πis given by (52), show
1771 that (54)|4α=↓|4(55).|'{A3}|π|≡3|≡0|≡.|9|4|ε[HM|*/|↔L|↔P|\]|9
1773 |πThe following modi_cation of Euclid's algorithm
1779 is often suggested: Instead oxfnrepwcing |εv
1785 |πby |εu|4|πmod|4|εv |πduring the division step,
1791 replace it by |¬G(|εu|4|πmod|4|εv)|4α_↓|4v|¬G
1795 |πif |εu|4|πmod|4|εv|4|¬Q|4|f1|d32|)v. |πThus,
1798 for exjmvle, if |εu|4α=↓|426 |πand |εv|4α=↓|47,
1804 |πwe have gcd|4(26,|47)|4α=↓|4gcd|4(|→α_↓2,|47)|4α=↓|4gcd|4(
1806 7,|42); |→α_↓2 |πis the remainder of smallest
1813 magnitude when multiples of 7 are subtracted
1820 from 26. Compare this procedure with Euclid's
1827 algorithm; estimate the number of division steps
1834 this method saves, on the av¬jj∧e.|'{A3}|≡3|≡1|≡.|9←4|ε[[|*/*3
1840 ↔1|↔**C\*4]9*3π*4und thes``≤brfz case-',of thesmodi_≡ation
1844 of Euclid'? algorithm su∧gestedfin exejccues3π;?wyaz
1849 ard thyssx∧llesyhinvuty |ε≥U44¬}Y4#V44¬Q|41λ|πwhicm
1852 requurds|ε↔ |π-uvisugn szeps?←'{A3}|≡3|≡2←≡.|9|4←ε[|*/|↔|↔cN\
1854 ]|9|π(a) AsMorse codessequefcdsofslefgth |εn
1858 |πis a string of |εr |πdots and |εs |πdashes,
1867 where |εr|4α+↓|42s|4α=↓|4n. |πFor example, the
1872 Morse code sequences of length 4 are|'{A6}αo↓|4αo↓|4αo↓|4αo↓
1879 |4,|4αo↓|4αo↓|4#|4,|4αo↓|4#|4αo↓|4,|4#|4αo↓|4αo↓|4,|4#|4#|;
1880 {A6}|πNoting thawhhhesconmpckafo pvgqxmmcawp|ε\Sβ4)Fβ1,]4)Fβ
1882 2,|4xFβ3,|4x|β4)|4α=↓|4x|β1x|β2x|β3)|β4|4α∃↓|4xFβ1*2Fβ2←4~↓*34
1882 xFβ1*2Xβ4←4αα+↓|*?*?*?|4α+↓|4x|β1x|β4|4α+↓|4x|β3x|β4|4α+↓|41,
1883 |π_nd and prove a simple relation between |εQ|βn(x|β1,|4.|4.
1890 |4.|4,|4x|βn) |πand Morse code sequences of length
1897 |εn. |π(b) (L. Euler, |εNovi Comm. Acad. Sci.
1905 Pet. |π|≡9 (1762), 53<69.) Prove that |εQ|βm|βα+↓|βn(x|β1,|4
1911 .|4.|4.|4, x|βm|βα+↓|βn)|4α=↓|4Q|βm(x|β1,|4.|4.|4.|4,
1913 x|βm)Q|βn(x|βm|βα+↓|β1,|4.|4.|4.|4, x|βm|βα+↓|βn)|4α+↓|4Q|βm
1914 |βα_↓|β1(x|β1,|4.|4.|4.|4, x|βm|βα_↓|β1)Q|βn|βα_↓|β1(x|βm|βα
1915 +↓|β2,|4.|4.|4.|4, x|βm|βα+↓|βn).|'{A3}|π|≡3|≡3|≡.|9|4|ε[M|*/
1917 |↔L|↔P|\]|9|πLet |εh(n) |πbe the number of representations
1924 of |εn |πin the form|'{A6}|εn|4α=↓|4xx|¬S|4α+↓|4yy|¬S,!!x|4|
1929 ¬Q|4y|4|¬Q|40, x|¬S|4|¬Q|4y|¬S|4|¬Q|40, |πgcd(|εx,|4y)|4α=↓|
1931 41, |πinteger |εx, x|¬S, y, y|¬S.|;{A6}|π(a)|9Show
1938 that if the conditions are relaxed to allow |εx|¬S|4α=↓|4y|¬
1946 S, |πthe number of representations is |εh(n)|4α+↓|4|"l(n|4α_
1952 ↓|41)/2|"L. |π(b) Show that for _xed |εy|4|¬Q|40
1959 |πand |ε0|4|¬W|4t|4|¬E|4y, |πwhere gcd|ε(t,|4y)|4α=↓|41,
1963 |πand for each _xed |εx|¬S |πsuch that |εx|¬St|4|"o|4n
1971 |π(modulo |εy) |πand |ε0|4|¬W|4x|¬S|4|¬W|4n/(y|4α+↓|4t),
1975 |πthere is exactly one representation of |εn
1982 |πsatisfying the resyrictions of (a) and the
1989 condition x|4|"o|4t (modulo |εy). |π(c) Consequently|'
1995 {A6}|εh(n)|4α=↓|4|↔k|4|↔d|↔a|(n|d2y|4α+↓|4t|)|4α_↓|4t|¬S|↔s|
1995 1|(1|d2y|)|↔f|4α_↓|4|"l(n|4α_↓|41)/2|"L,|;{A6}|πwhere
1997 the sum is over all positive integers |εy, t,
2006 t|¬S |πsuch that gcd(|εt,|4y)|4α=↓|41, t|4|¬E|4y,
2011 t|¬S|4|¬E|4y, tt|¬S|4|"o|4n (|πmodulo |εy). |π(d)
2016 Show that each of the |εh(n) |πrepresentations
2023 can be expressed uniquely in the form|'{A6}|εx|4α=↓|4Q|βm(x|
2030 β1,|4.|4.|4.|4,|4x|βm),!!y|4α=↓|4Q|βm|βα_↓|β1(x|β1,|4.|4.|4.
2030 |4,|4x|βm|βα_↓|β1),|;{A4}x|¬S|4α=↓|4Q|βk(x|βm|βα+↓|β1,|4.|4.
2031 |4.|4,|4x|βm|βα+↓|βk)d,!!y|¬S|4α=↓|4Q|βk|βα_↓|β1(x|βm|βα+↓|β
2031 2,|4.|4.|4.|46,|4xxxxxxxxx*?*?*?*?k|βα_↓|β1(x|βm|βα+↓|β2,|4.|4.|
2031 4.|4,|4x|βm|βα+↓|βk)d,|;{A6}|πwhere |εm, k, d,
2036 |πand the |εx|βj |πare positive integers with
2043 |εx|β1|4|¬R|42, x|βm|βα+↓|βk|4|¬R|42, |πand |εd
2047 |πis a divisor of |εn. |πThe identity of exercise
2056 32 now implies that |εn/d|4α=↓|4Q|βm|βα+↓|βk(x|β1,|4.|4.|4.|
2060 4, x|βm|βα+↓|βk). |πConversely, every sequence
2065 of positive integers |εx|β1,|4.|4.|4.|4, x|βm|βα+↓|βk
2070 |πwith |εx|β1|4|¬R|42, x|βm|βα+↓|βk|4|¬R|42,
2073 |πand |εQ|βm|βα+↓|βk(x|β1,|4.|4.|4.|4, x|βm|βα+↓|βk)
2076 |πdividing |εn, |πcorresponds in this way to
2083 |εm|4α+↓|4k|4α_↓|41 |πrepresentations of |εn.
2087 |π(e) Therefore |εnT|βn|4α=↓|4|"l(5n|4α_↓|43)/2|"L|4α+↓|42h(
2089 n).|'{A3}|≡3|≡4|≡.|9|4|ε[HM|*/|↔M|↔c|\]|9|π(H.
2091 Heilbronn.) (a) Let |εh|βd(n) |πbe the number
2098 of representations of |εn |πas in exercise 33
2106 such that |εxd|4|¬W|4x|¬S, |πplus half the number
2113 of representations with |εxd|4α=↓|4x|¬S. |πLet
2118 |εg(n) |πbe the number of representations without
2125 the requirement gcd|ε(x,|4y)|4α=↓|41. |πProve
2129 that|'{A6}|εh(n)|4α=↓|4|↔k|uc|)d|¬Dn|)|4|≤m(d)g|↔a|(n|d2d|)|
2130 ↔s,!!g(n)|4α=↓|42|4|↔k|uc|)d|¬Dn|)|4h|βd|↔a|(n|d2d|)|↔s.|;
2131 {A6}|π(b)|9Genejjwizing exdrcise 33b, show that
2136 fbr |εd|4|¬R|41, h|βd(n)|4α=↓|4|¬K|4(n/|≥1y(y|4α+↓|4t)|≥2|≥2
2138 |4α+↓|4O(n), |πwhere the sum is over all integers
2146 |εy, t |πsuch that gcd|ε(t,|4y)|4α=↓|41, 0|4|}¬QI5|4|¬E|4y|4
2151 |¬W|4|¬H|v4n/d|)|1.|'|π(c)|9|1|1Show that |¬K|4(||ε|≥1y/(y|4
2154 α+↓|4t)|≥2|4α=↓|4|≤'(y)|4|πln|42|4α+↓|4|εO(|≤s|βα_↓|β1(y)|≥2
2154 , |πwhere the sum iusover the range |ε0|4|¬W|4t|4|¬ES4y,
2162 |πgcd(|εt,|4y)|4α=↓|41; |πand |ε|≤s|βα_↓|β1(y)|4α=↓|4|¬K|4(|
2164 βd|β|¬D|1|βy1/d).|'|π|π(d)|9Show that |¬K|ur|ε|)1|¬Ey|¬En|)|
2167 ≤'(y)/y|g2|4α=↓|4|¬K|ur|)1|¬Ed|¬En|)|≤m(d)H|ur|)|"ln/d|"L|)/
2167 d|g2.|'|π(e)|9|1Hefce |εT|βn|4α=↓|4(12|4|πln|42/|ε|≤∀|g2)|≥1
2169 |πln|4|εn|4α_↓|4|¬K|βd|β|¬D|βn|*/|≤!|\(d)/d|≥2|4α+↓|4O(|≤s|βα
2169 _↓|β1(n)|g2|≥2.←'{A3|π|≡3|≡5|≡.|9|4|ε[HM|*/|↔M|↔O|\]|9|π(A.
2170 Yao and D. E. Knuth.) Prove thaz the sux of all
2181 pajtial quotientssfbr the fractionf |εm/n,,p54|¬ES4m|4|¬W|4n
2185 , |πis equal to 2(|¬K|4|"⊂|εx/y|"L|4α+↓N4←.∩n/2|"L),n|πwhere
2189 the sum is over all representations |εn|4α=↓|4xx|¬S|4α+↓|4y
2196 y|¬S |πsatisfying the conditions of exercise
2202 33(a). Show that |¬K|4|"l|εx/y|"L|4α=↓|43|≤p|gα_↓←g2n(|π⊂n|4
2205 |ε↔)←g2]4α~↓|4O(,|4|πlog|4|εn(|πlog|4log|4|εn)|g2|≥2,
2206 |πand apply this to the ``_fcieno'',formnof Eucgids'
2213 algorithm which uses only subtraction instead
2219 of division.|'{A3}|≡3|≡6|≡.←9←4←ε[M|*/|↔L|↔C|\]|9|π(G.,H.
2222 Brad∧ey.)↔Wyaz iushhessxkwlwsz vjwqusoff|\≥Uicn|[)ukv
2225 hhqwhthescjwculwwivn ofsgcdSε(≡|β1,←4.|4.|4.←4,|4u|βn)
2227 |πby steps C1, C2 in Section 4.5.2 |π⊃equires
2235 |εN |πdivisions, if Euclid's algorithm is used
2242 throughout? Assumesthat |ε]|4|¬R|4/.←'{A3}|≡3|≡7|≡.|9|4|ε[M|
2244 */|↔L|↔l|\]|9|π(T. S. Motzkin and E. G.λStraus.)
2250 Lez |ε_Si1,]4.]4.|4.←4,]4a|βn |πbe positive integers.
2255 Show that max|4|εQ|βn(a|βp|β(|β1|β),|4.|4.|4.|4,
2258 a|βp|β(|βn|β)), |πover all permutations |εp(1)|4αo↓|4αo↓|4αo
2262 ↓|4p(n) |πof |ε|¬T1,|42,|4.|4.|4.[46]4n|¬Y, |πoccurs
2266 when |εa|βp|β(|β1|β)|4|¬R|4a|βp|β(|βn|β)|4|¬R|4a|βp|β(|β2|β)
2267 |4|¬R|4a|βp|β(|βn|βα_↓|β1|β)|4|¬R|4αo↓|4αo↓|4αo↓|4;
2268 |πand the minimum occurs when |εa|βp|β(|β1|β)|4|¬E|4a|βp|β(|
2273 βn|β)|4|¬E|4a|βp|β(|β3|β)|4|¬E|4a|βp|β(|βn|βα_↓|β2|β)|4|¬E|4
2273 a|βp|β(|β5|β)|4|¬E|4αo↓|4αo↓|4αo↓|4|¬E|4a|βp|β(|β6|β)|4|¬E|4
2273 a|βp|β(|βn|βα_↓|β3|β)|4|¬E|4a|βp|β(|β4|β)|4|¬E|4a|βp|β(|βn|β
2273 α_↓|β1|β)|4|¬E|4a|βp|β(|β2|β).|'{A3}|π|≡3|≡8|≡.←9|4|ε[M|*/*3↔P
2274 |↔C|\]|9|π(J. Mikusinski.) Let |εK(n)|4α=↓|4|πmax|ur|)|εm|¬R
2277 0|)|4T(m,|4n). |πTheorem F shows that |εK(n)|4|¬E|4←"l|πlog|
2282 β|≤f(|¬Y|v45|)←1←1n|4α+↓|41)|"P|4α_↓|42; prove
2284 that |εK(n)|4α=↓|4|f1|d32|)|1|"p|πlog|ε|β|≤f|4(|¬H|v45|)|1|1
2285 n|4α+↓|41)|"P|4α_↓|42.|'{A3}|π|≡3|≡9|≡.|9|ε[M|*/|↔P|↔C|\]|9|π
2286 (R. W. Gosper.) If a baseball player's bathing
2294 average is .334, what is the fewest possible
2302 number of times he has been at bat? [Non-baseball-fans:
2311 Batting average|4α=↓|4(number of hits)/(times
2315 at bat), rounded to three dekimal places.]|'|Ha*?*?{U0}{H10L12
folio 476 galley 4
2322 M29}|πW58320#Computer|9Programming!ch. 4!f. 476!g.
2325 4|'{A6}|∨4|∨.|∨5|∨.|∨4|∨.|9|∨F|∨a|∨c|∨t|∨o|∨r|∨i|∨n|∨g
2327 |∨i|∨n|∨t|∨o |∨P|∨r|∨i|∨m|∨e|∨s|'{A6}Several
2330 of the computational methods we have encountered
2337 in this book rest on the fact that every positive
2347 integer |εn |πcan be expressed in a unique way
2356 in the form|'{A6}|εn|4α=↓|4p|β1p|β2|4.|4.|4.|4p|βt,!!p|β1|4|
2359 ¬ES4p|β2|4|¬E|4|¬O|4|¬O|4|¬O|4|¬E|4p|βt,|J!(1)|;
2360 {A6|πwhere each |εp|βkf|π/s prime),(Wyefn|εn|4α*245#,|πohis
2364 eqqation holds for |εt|4α=↓|40.) |πIt is unfortunately
2371 not a simvlasmattejcto _≡dfthiuspvcmdsfkkgorczawionnmxn|εn,n
2374 |πor to determine whether or not |εn |πis prime)λSo
2383 fajnas _fxbmdskfo∧q↔,ip is asggdaz ddal hajddjntonfkcoor
2389 aslajgesnkmber |ε≡n|πohafnhoncomvqqzsthesvrjawesy
2391 cvmmmmnfkvvsbrcmxfhwb lajgesnkxbdrf |ε)n|[_kdn|≥*2);|["hzjjfb
2393 rjsqassym¬q∧ a¬gckffactorcngnlajgdsnu¬bejs wyeff¬djcpmxsub∧z
2395 ).X¬z ss¬brawpicgencokssqwys tonsimplify thesfactoring
2399 problem havesbeefndkukovjjjd↔,akdfweswqplpno∧yicv¬szpg∧tessx
2400 mxsmfnthex.]']''|≡DF≡≡I≡vN≡c|≡d|≡ds|≡aS≡,|≡-f|≡f|≡≠S≡c|≡t|≡~
2400 |≡r|≡.|9|4First let us confujdrnthesmofyhmb¬cgkusuwgggcphmmf
2403 xgcfkkvogcqwwpvm(;Iff|≥*2N4|¬}S41, |π∧z can divide
2407 |εn |πby successivesprimess|εp|4α=↓|42, 3,λ5,|4.]4.←4.
2411 |πuntil discovering the smawlast |ε≥i|πforcwqich
2416 |ε↔N4|π.odS4|ε≥I4↓≡↓N4that |εn|4|πmod|4|εp|44=|↔6α*2↓(40
2418 |[~kt |ε|"ln/p|"L|4|¬E|4p, |πwe can conclude
2423 that |εn |πis prime; for if |εn |πis not prime
2433 then by (1) we must have |εn|4|¬R|4p|=|β1|g2,
2440 |πbut |εp|β1|4|¬Q|4p |πimplies that |εp|=|β1|g2|4|¬R|4(p|4α+
2444 ↓|41)|g2|4|¬Q|4p(p|4α+↓|41)|4|¬Q|4p|g2|4α+↓|4n|4|πmod|4|εp|4
2444 |¬|4|"ln/p|"L|1p|4α+↓|4n|4|πmod|4|εp|4α=↓|4n.
2445 |πThis leads us to the following procedure:|'
2452 |'{H9L11}|≡F|≡i|≡g|≡. |≡1|≡0|≡.|9|4A simple factoring
2457 algorithm.|;|'{H10L12}|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m
2460 |≡A (|εFactoring by division).|9|4|πGiven a positive
2466 integer |εN, |πthis algorithm _nds the prime
2473 factors |εp|β1|4|¬E|4p|β2|4|¬E|4|¬O|4|¬O|4|¬O|4|¬E|4p|βt
2475 |πof |εN |πas in Eq. (1). The method makes use
2485 of an auxiliary sequence of ``trial divisors''|'
2492 {A6}|ε2|4α=↓|4d|β0|4|¬W|4d|β1|4|¬W|4d|β2|4|¬W|4d|β3|4|¬W|4|¬
2492 O|4|¬O|4|¬O|4,|J!(2)|;{A6}|πwhich includes all
2496 prime numbers|4|¬E|4|¬H|v4|εn|) |π(and which
2500 may also include values which are |εnot |πprime,
2508 if it is convenient to do so). The sequence of
2518 |εd'|πs must also include at least one value
2526 such that |εd|βk|4|¬Q|4|¬H|v4n|)|1.|'{H10L12}|π!|9|4|1|1|1Ho
2529 w many trial divisions are necessuj¬ in Algorithm
2537 A? Let |ε|≤p(x) |πbe the number of primes|4|¬E|4|εx,
2545 |πso that |ε|≤p(2)|4α=↓|41, |≤p(10)|4α=↓|44;
2549 |πthe asymptotic behavior of this function has
2556 been studied exbensivewysxxsmanxsofftheswbrgd-↔
2559 grdatest mathematicians, beginning with Legendre
2564 in 1798. Charles de la Vall|=1ee Poussin proved
2572 in 1899 that, for some |εA|4|¬Q|40,|'{A6}|ε|≤p(x)|4α=↓|4|↔j|
2578 urx|)2|)|4|(dt|d2|πln|4|εt|)|4α+↓|4O(x|πe|urα_↓|εA|¬H|πlog|1
2578 |1|ε)|)←)))←J!(3)*4;↓A6}F['[|εM|=1em. Couronn|=1es
2580 Acad. Roy. Belgique |π|≡5|≡9 (1899), 1<74.] |πIntegrating
2587 by parts yields|'{A6}|ε|ε|≤∀())*34α=↓|4←(x|d2|πln|4|εx|)]4α~↓
2590 |4|(x|d2|π(lnN4|εx)|g2←)|4α+↓|4|(2*3|1|1x|d2(|[πvN4|εx)*4g3|)|
2590 4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|(r*3|1|1x|d2|π(ln|4|εx)|gr|gα+↓|g1
2590 |)|4α+↓|4O|↔a|(x|d2(|πlog|4x)|gr|gα+↓|g2|)|↔s|J!(4)|;
2591 {A6}|πfor all _xed |εr|4|¬R|40. |πThe error term
2598 in (3) can be improved, for example to |εO(x|4|πexp(|→α_↓|εA
2606 (|πlog|4|εx)|g3|g/|g5/(|πlog|4log|4|εx)|g1|g/|g5)|≥2;
2607 |πsee A. Wal_sz, |εWeyl'sche Exponentialsummen
2612 in der neueren Zahlentheorie |π(Berlin,λ1963),,Chapter
2617 5.λBejnhardfRiemannnconjectured in 1859 that|'
2621 {A6}|ε|≤p(x)|4α=↓|4|↔k|uc|)k|¬R1|)|4|≤m(k)L(k|¬H|v2x|))/k|4α
2621 +↓|4O(1)|4α=↓|4L(x)|4α_↓|4|f1|d32|)L(|¬H|v2x|))|4α_↓|4|f1|d3
2621 3|)L(|¬H|v2x|))|4α+↓|4|¬O|4|¬O|4|¬O!(5)|?{A6}|πwyere
2623 |ε1())|I6α≡4|¬J|ujx|)2|)|4dt/|πln|4|εt, |πand
2625 his formula agrees well with actual counts. For
2633 example, we have the follo∧ing table:|'|'⊗|∂!!!|∂!!!!!|∂$!!!
2640 !!|∂>!!!!!|∪>!!!!!!!!|∪4SS;;|>|εx|;|≤p(x)|;x/|πln|4|εx|;
2646 L(x)|;|πRiemann's|4formuwa|;>↓A2}|>10|g3|;168|?
2652 144.8|?176.6|?168.36!|9|?>|>10←g6|;78498*3|↔7382.4|?
2659 78626.5←?78527.40!|9|*3=∂|>10|g↓::\0840847455.43!|9|?
2661 >{A12}Actually Riexann's conjecture was disproved
2667 by J. E. Littlewood in 1914; see Hardy and Littlewood,
2677 |εActa Math. |π|≡4|≡1 (1918), 119<196, where
2683 it is shown that there is a positive constant
2692 |εC |πsuch that |ε|≤p(x)|4|¬Q|4L(x)|4α+↓|4C|¬H|v2x|)
2696 |πlog log log|4|εx/|πlog|4|εx |πfor in_nitely
2701 many |εx. he|πBut Riemann made another much more
2709 plausiblesconjekture,λthesfamous ``Riemann hypothesis''
2712 about the complex zeros of the zeta function;
2720 this hypoohesis↔λif true↔λwould imply that |ε|≤p(x)|4α=↓|4L(
2725 x)|4α+↓|4O(|¬H|v4x|)←4|πlog|4|εx).|'|π!|9|4|1|1←14cnordejcho
2726 nakjwqzeshhesa¬jjj∧jsbdyu¬cgrcmxfUWgggcphmmU**,qwsq∧¬q∧fppkks
2726 homkkm∧qhm∧qpwjg∧shhyspwjg∧syhpvcvxsfkkvogc \≥Pilh|[≤qplphzf
2727 ffhomxb).HHpusqqusypvmnqwus=≠ky *2inveszigated
2729 by Kajg Dkck¬jn |ε[**Jkkv fS=*/"r M}w.,,Auyggm..,mvvhFxy.,
2735 |π|≡↑↑222222222222222222222222222222222222222222222222222222
2735 2n., och Fys. |π|≡2|≡2|≡A|≡, 10 (1930), 1<14],
2742 who studied the probability that a random integer
2750 between 1 and |εx |πwill have its largest prime
2759 factor|4|¬E|4|εx|g|≤a. |πDickman gave a heuristic
2764 argument to show that this probability approaches
2771 the limiting value |εF(|≤a) |πas |εx|4|¬M|4|¬X,
2777 |πwhere |εF |πcan be calculated from the functional
2785 equation|'{A6}|εF(|≤a)|4α=↓|4|↔j|ur|≤a|)0|)|1|1F|↔a|(t|d21|4
2786 α_↓|4t|)|↔s|(dt|d2t|)|1|1,!!0|4|¬E|4|≤a|4|¬E|41;!!F(|≤a)|4α=
2786 ↓|41 for |≤a|4|¬R|41.|J!(6)|;{A6}|πHis argument
2791 was essentially this: The number of integers
2798 |¬E|εx |πwhose largest prime factor is between
2805 |εx|gt |πand |εx|gt|gα+↓|gd|gt |πis |εxFαO↓(t)dt.
2810 |πThe number of primes |εp |πin that range is
2819 |ε|≤p(x|gt|gα+↓|gd|gt)|4α_↓|4|≤p(x|gt)|4α=↓|4|≤p(x|gt|4α+↓|4
2819 (|πln|4|εx)x|gtdt|≥2|4α_↓|4|≤∀(x|gt)|4α=↓|4xSgtdt/t.
2820 |πFor every such |ε≥/λ|π"hesnkxbdjcofsicmegerfs|ε≡n|πsukv
2824 that |ε,p|4|¬E|4)s|πand the largest prime factor
2830 of |εn |πis |ε|¬Ep |πis the number of |ε↔|4|¬ES4*2Fg3|gα_↓|gt
2838 |π≤yofespwjgdsz pccvdsfjkvorniss|¬J(*4ε)Fg3←gα_↓|gt)*3gg|g/6g
2840 (V3←gα≠↓**vo|g))n|π,jmdwqs|ε*2Fv3|gα≠↓*4goF(o/(↓←4α≠↓|4t)|≥2.λ|
2840 π[efce |ε)Fαα↓(t)-b|4α=↓|4()Sgtdt/+)()Sg1←gα≠↓**goF|≥*5+/(↓→4≠
2841 ↓|4+)(≥↑,,|π≠kff(**) fxglg∧ssbysicoe∧rjwign.λThiushyujcszic
2843 ajgkment can be made rigorous; V. Ramaswami |ε[Bu..
2851 Amer. Math. Soc. |≡5|≡5 (1949), 1122<1127] |πshowed
2858 that the probabilitysin question for _xed |ε|≤a
2865 |πiss|εF(|≤≠)*34α+↓|4O(1/|πlog|4←ε)),|πas |εx|4|¬M|4|¬X,
2867 |πand mafy othejnauthors have extended the analysis
2874 [see the survey by Karl K. Norton, |εMemoirs
2882 Amer. Math. Soc. |π|≡1|≡0|≡6 (1971), 9<27].|'
2888 !|9|4|1|1|1If |f1|d32|)|4|¬E|4|ε|≤a|4|¬E|41,
2890 |πformula (6) simpli_es to|'{A6}|εF(|≤a)|4α=↓|41|4α_↓←4|↔j|u
2894 r1←)|≤aS)|1|1F|↔aS(t|d21|4α_↓|4t|)|↔?|(dt|d2t|)|4α=↓←41|4α_↓
2894 |4|↔jNur1|)|≤_|)|4|(-t|d2t|)|4≡↓|41←4α+↓|4|πln|4|ε|≤a.←;{A6S
2894 πThus, fbrcexjmple,λthesprgbabkpilyshhqwhuucjkfbmnpvxuppv¬si
2895 cme∧jjn|¬E|≥xf|π.qusa prcvxsfkktorc|¬}|¬Y|v64ε*2F)↔|π/us|≥*544
2896 ≠↓**4**((f↓5f↓26))*44↓≡44[∩vN46/,u∧b¬qh6;pqjckfm..Icnuwlpsukvhc
2896 kuss↔,AwgorithmmA must work hard.|'|H*?*?*?*?{U0}{H10L12M29}|πW5
folio 479 galley 5 WARNING: Tape mostly unreadable, NEXT TEN GALLEYS.
2900 8320#Computer Programming!ch. 4!f. 479!g. 5|'
2905 {A6}|π!|9|4|1|1|1The net result of this discussion
2911 is that Algorithm A will give the answer rather
2920 quickly if we want to factor a six-digit number;
2929 but for large |εN |πthe amount of computer time
2938 for factorization by trial division will rapidly
2945 exceed practical limits, unless we are unusually
2952 lucky.|'!|9|4|1|1|1|πLater in this section we
2958 will see that there are fairly good ways to determine
2968 whether or not a reasonably large number |εn
2976 |πis prime, without trying all divisors up to
2984 |ε|¬H|v4n|)|1. |πTherefore Algorithm A would
2989 often run faster if we inserted a primality test
2998 xbzween steps A2 and A3; the running time fogchhis
3007 imvvoved algorithm will be roughly proportional
3013 to |εp|βt|βα_↓|β1, |πthe |εsecond-largest |πprime
3018 factor of |εN, |πinstead of to max(|εp|βt|βα_↓|β1,|4|¬H|v4p|
3024 βt|)|1). |πBy an argument analogous to Dickman's
3031 (see exercise 18), we can show that the second-largest
3040 prime factor of a random integer |εx |πwill be
3049 |¬E|εx|g|≤b |πwith approximate probability |εG(|≤b),
3054 |πwhere|'{A6}|εG(|≤b)|4α=↓|4|↔j|ur|≤b|)0|)|1|1|↔aG|↔a|(t|d21
3055 |4α_↓|45H(*4↔s|4α_↓|4F|↔a|(t|d21|4α_↓|4t|)|↔s|↔s|(dt|d2t|)N1H
3055 5#,|πfogn|ε0|4|¬E|4|≤bN4|¬E|4|f1|d32|);!!|εG(|≤b)|4α=↓|41
3056 |πfor |ε|≤b|4|¬R|4|f1|d32|).|J!(7)|;{A6}|π(See
3059 Fig. 11.) Numerical evaluation of (6) and (7)
3067 yields the following ``percentage points''|1:|'
3072 |'{H9L11}|∂!!!!!|9|1|1|1|∂!!!|∂!!!|∂!!!|∂!!!|∂!!!|∂!!!|∂!!!|
3073 ∂!!!|∂!!!||∂!!!!!!!!!!!!!!!|∂$!!|∂|E|'|>|εF(|≤a),|4G(|≤b)α=↓
3075 |4|?|4.01|'.05|'.10|'.20|'.35|'.50|'.65|'.80|'
3084 .90|'.95|'.99|'>|>|ε|≤a|4α=↓|?|4.2697|'.3348|'
3092 .3785|'.4430|'.5220|'.6065|'.7047|'.8187|'.9048|'
3099 .9512|'.9900|'>|>|≤b|4α=↓|?|4.0056|'.0273|'.0531|'
3107 .1003|'.1611|'.2117|'.2582|'.3104|'.3590|'.3967|'
3114 .6517|'2{J12}{H10L12d|πThus,λthe second-largest
3117 prime factor will be less than |εx|g.|g2|g1|g2
3124 |πabout half the time, etc.|'!|9|4|1|1|10hes|εnuxbdj,
3130 t, |πofsprimesfjkoors hassalsbnbdef intensively
3134 analyzed. Ob¬couslys|ε1|4|¬E|4t|4|¬E|4|πlg|4|εN,
3136 |πbut these lower and upper bands are seldom
3144 achieved. It is possible to prove that a random
3153 integer between 1 and |εx |πhas |εt|4|¬E|4|πln|4ln|4|εx|4α+↓
3159 |4c|¬H|v4|πln|4ln|4|εx|) |πwith the limiting
3163 probability|'{A6}|ε|(1|d2←¬H|v22|≤p|)|)|4|↔j|urc|)α_↓|¬X|)|1
3164 |πe|gα_↓|ε|gu|i2|g/|g2|4du|;{A6}|π|πas |εx|4←¬X|4←¬X,
3167 |π↔br afxs=*2xdf|≥*2#.|[7Cnmohyjcq∧gjf↔,hhysfkuygc¬¬qpvmnmxf|≥
3168 εh|[#ussssefopuwlqsnorv¬w#,wulhhmdaknukffvkjcukcjspvN4∀vN44≥
3168 *2);|[≤∧b¬t 99.7777777777777777777777777777777777777*?3
3171 pqdrcentnxfall icoegers|4|¬E|4|εx |πhave |ε|¬Gt|4α_↓|4|πln|4
3174 ln|4←ε)|¬G|4←¬E|43|¬H|v4|πln|4ln|4|εx|)|1. |πFurthermore
3176 the average value of |ε←¬Gt|4α_↓|4|πln|4ln|4←ε)|¬G
3181 |πis |ε|≤gN4α+↓*44←¬KSuurN)p|¬FS)←4(←π∩c(1|4α_↓|4|ε*5/∀)|4α"↓|
3182 41/(p|4α_↓|41)|≥2|4α=↓|41.03465 388*58 9763↑.
3185 [←π6K)λG.λH[.Hujjxyukff).M[.Q∧cvvh.,|≥\cmggbkkvpvmnhomhhysHh
3185 sbr¬ymxfNkxbdjk↔λ|π4th ed),(αxfbrj↔,1*5**3)↔,|≤↑↑2#31≥?P7,EjjF
3186 =*/#xsukffM..Kkk/,|≥*5¬xj#.K*2.M¬wh..|[[≡↑]≡**/(*5*/0)↔,77↑<66#[]I
3186 P fxglg∧qshhqwhUwgggcphmmUUuuuuwlqy=≡ffsuuffwqsx¬wlpfkkvogks
3187 ukffhhyfnxb∧vcfsuupgnv≤-jjwk-~kqhssajcvhfxgchhysmohyjk)[,]]'
3187 |≡**|≡_U≡≡N≡+|≡~|≡r|≡i|≡n|≡g |≡a |≡l|≡a |≡M|≡"|≡n|≡~|≡e
3191 |≡**C≡≠S≡≠C≡*2P≡&oN≡*2]::46fajchhssxb∧vcnccvvmxfCvqqpzjc7#,qwsm
3191 bxsjv¬dfhhqwh,`↑ucjkfbmmnk¬xbjcv∧ffjjwogccvmxsfnuwhcjkfbmmiu
3191 f,"hv¬j¬ycjkfbmm.',hHpuspvcccciple, which worked
3194 againsz us in that chaqter, hausthe rjddexingcvvcgqushhqwhil
3200 lwajfshomuusukvvcuucvgqys∃*2cufmhmxzhmbfmxffkkvogcpwwpvm,,fk
3201 ikvvvjrdfcjwhhdccjkkdntlynxynJ. M. Pollary bbswell
3205 ufder |εN|g1|g/|g6#]'!|9←445←1455[3et |εf(x)λ|π~dsukxspggqfm
3207 mvuwpquth icmz∧∧jccvb∃*2cufmy↔,ukffcvmfukdjchhysssqqufckssfd_
3208 ≡fdfxxy]≤{**}\εxXI1→44\YI⊂→44*/\:!XXIvmI∧α≤I⊂54*2I**x(xIcm)|1|1|
3208 1N[mod|4|εN,!!y|βm|βα+↓|β1|4α=↓|4f(y|βm)*44|πmodF44ε∀,←JJ((((
3208 :J**}[πwqyjjs \≥p [7usukxypvcvxsfkkvogcmxf Q*2M.
3212 M7Ihnxolgows that|'{A6}|*?*?*?*?y|βm|4α=↓|4x|βm|4|πmod|4|εp,!|πf
3214 or |εm|4|¬R|41.|J!(9)|;{A6}|πNow exercise 3.1<6
3219 shows that we will have |εy|βm|4α=↓|4y|β2|βm
3225 |πfor some |εm|4|¬R|41; |πthus |εx|β2|βm|4α_↓|4x|βm
3230 |πwill be a multiple of |εp. |πFurthermore if
3238 |εf(y)|4|πmod|4|εp |πbehaves as a random mapping
3244 from the set |ε|¬T0,|41,|4.|4.|4.|4,|4p|4α_↓|41|¬Y
3248 |πinto itself, exercise 3.1<12 shows that the
3255 average value of the least such |εn |πwill be
3264 of order |ε|¬H|v4∀|)←1. |πIn fact,λthis averagesvalue
3270 for random mappings turns out to be|'{A6}|ε|↔aS(|≤≥|g26d↑32]
3277 )*44α~↓N4ON↔j|(|πlog|4|εp|d2p|)|↔s|↔sQ(p)|4α=↓|4|↔H|(|≤p|g5p|
3277 d2288|)|4α_↓|4|(←≤∀|g2|d↑48|)|4α+↓|4O|↔a|(|πlog|4|εp|d2|¬H|v
3277 2∀|)|)|↔?SJ!(10)*4;{A6}|π'wheresthe funcgionn|ε\s|π∧as
3279 de_≡dd innSskoionn1.2.11.3 (see exercise 4).λIf
3284 the di=erent prime divisors of |εN |πcorrespond
3291 to di=erent values of |εm |π(as they almost surely
3300 will, when |εN |πis large), we will be able to
3310 _nd them by calculating gcd(|εx|β2|βm|4α_↓|4x|βm,|4N)
3315 |πfor |εm|4α=↓|41, 2, 3,|4.|4.|4.|4, |πuntil
3320 the unfactored residue is prime.|'!|9|4|1|1|1From
3326 the theory in Chaptern3, we know that a linear
3335 polynomial |εf(x)|4α=↓|4ax|4α+↓**4c |πwill not
3339 be su∃ciently random for our purposes. The next-simplest
3347 case is quadratic, say |εf(x)|4α=↓|4x|g2|4α+↓|41;
3352 |πalthough we don't |εknow |πthat this function
3359 is su∃ciently random, our lack of knowledge tends
3367 to support the hypothesis of randomness, and
3374 empirical tests show that this |εf |πdoes work
3382 essentially, as predicted. In fact, |εf |πis
3389 probably slightly |εbetter |πthan random, since
3395 |εx|g2|4α+↓|41 |πtakes on only |f1←d32|)(*3ε∀|4α+↓|41)
3400 |πdistinct vawues mod|4|εp.]'⊗|,'|π|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|
3402 ≡m |≡B |≡(|≡M|≡o|≡n|≡t|≡e |≡C|≡a|≡r|≡l|≡o |≡f|≡a|≡c|≡t|≡o|≡r
3406 |≡i|≡z|≡a|≡t|≡i|≡o|≡n|≡)|≡.!This algorithm outputs
3409 the prime factors of a givennintegej |εN|4←¬J|42,,|π≤uth
3416 higm probability, althok∧h theresis a chance
3422 it will fail.|'{A3}{I1.8H}|≡B|≡1|≡.|9(4nitialize)]|9*3et
3426 |εx|4←¬{|46/,x|¬FS4←¬{|45/,n|4←¬WI46.,(*4πDuringcthis
3427 awggrithm, |εn |πiusthe unfactored part of |ε*4,λ|πafdf|ε(x↔←
3433 4)F¬S)↔|π⊃jqrjsefoss|ε(x|βmM4|πmod|4←εn, x|β2|βm|4|πmod|4|≥≡
3434 ) |πin (8), where |εf(x)|4α=↓←4)Fg2←4α+↓←41λ|πandf|ε%S4*2↓**45
3438 #)(,↓J↓j|π|≡B|≡↑]≡)|9[0esz primawity)]←9If |ε↔n|πissprime
3441 (seesthe disckssion below), output |εn; |πthe
3447 algorithm terminates.|'{A3}|≡B|≡3|≡.←9[Factornfbund?*4]9Set
3450 |εg|4|¬L|4|πgcd(|εx|¬S|4α_↓|4x↔]4n))λ|π6kf|ε≤C4α≡↓**45#,|π∩gm
3450 mmntonsyzqiB**≥;mohyj∧qussm¬qpqqh|≥∧#.|[[m∧uiff|ε≤C4α≡↓**4/,,|
3450 π"hesawgoriphmntervccjwzss(_fffil huusfkulwd↔,xdkkuussqeskkm
3451 ∧qhhqwh|≥*2n|[#uf,"hpvcvx)).Mohyj∧qusssszh|\≡N44¬}P46/#/,xX44
3451 ¬}I4*2X44[[mbF44≥*2,,xX}}S44}}P4X}}S44[[mbF44≥≡,,|[↓kffcjzqkcn
3451 homsyzqpX↓#.)(Mozshhqwh|≥≤v|[.¬qynmo xbspccvx;;hhpussym¬q∧fx
3452 bshzsyed).ICnhhyscjjjss¬¬fmhhhqwh|≥≤v|[#uf,"hpvcvx↔,{U0}{H10
folio 482 galley 6
3452 L12M29}|πW58320#Computer Programming!ch. 4!f.
3455 482!g. 6|'{A6}!|9|4|1|1|1As an example of Algorithm
3462 B, let's try to factor |εN|4α=↓|425852 |πagain.
3469 The second execution of step B3 will output |εg|4α=↓|44
3478 (|πwhich isn't prime). After four more iterations
3485 the algorithm _nds the factor |εg|4α=↓|423.|'
3491 !|9|4|1|1|1|πAlgorithm B has not distinguished
3496 itself in this example, but of course it was
3505 designed to factor |εbig |πnumbers. Algorithm
3511 A takes much longer to _nd large prime factors,
3520 but it can't be beat when it comes to removing
3530 the sxall ones)λIn prjktice,λwe should run Algorithm
3537 A awhile before switching over to Algorithm B.|'
3545 !|9|4←141←1*5ascan gez a bdzter iddasof Algorithm
3551 B's prowess by considejing thestefnpajgjsyhsu¬)-kvvphpvcmes:
3555 :HHysnk¬xbjcmffipzjjzivnf↔,|ε.(*4≤≠)↔,|πneeddd
3556 to _,d the factor |εp |πis|'{A6}|ε{H9L11}|∂!!!|9|1←1|1|∂!!!|
3562 :H∂!!!|9←∂$!!|9←∂$!!|9←∂$!!|9*3∂!!!|9←∂!!!|9|∂$!!|9|∂!!!|9|∂!
3562 !!|9|∂|E|'|44\≥↓≡44?9998**77*399988↓7*3:999977?:9{H10L12}|πThus
3563 we can probably factor almost all 12-digit numbers
3572 in less than 1000 iterations (compared to roughly
3580 100,000 divisions in Algorithm A). M. L. Wunderlich
3588 has found that |εm(p)|4|¬W|44|¬H|v4p|) |πfor
3593 all |εp|4|¬W|410|g6, |πand max|≥1|εm(|1p)|≥2|4α=↓|4m(967129)
3596 |4α=↓|43680 |πin this range.|'!|9|4|1|1|1The
3601 time-consuming operations in each iteration of
3607 Algorithm B are the three (multiprecision) multiplications
3614 and divisions in step B4 and the gcd in step
3624 B3. If the gcdfmveration is slow, Pollard suggests
3632 gaining speed by accumulating the product mod|4|εn
3639 |πof, say, ten consecutive |ε(x|¬S|4α_↓|4x) |πvalues
3645 before taking each gcd; this replaces 90 percent
3653 of the gcd "perations by a single multiplication
3661 and division while only slightly increasing the
3668 chance of faulure.λHesalso suggests starting
3673 wuth |εx|4|¬L|4)N¬S|4|¬L|4x|βq|4|πmod|4|εN |πin
3676 step B1,λwhere |εq |πis say |f1|d310|) the number
3684 of iterations one issplanning to use.←'!|9|4|1|1|15Cnhhose
3690 rare cases where failure occurs for large |εN,
3698 |πwe could try using |ε↔(x)(4*24*2XV∩64α"↓4/c|π)xgcsxmxs|ε/|4←
3702 =|↔6α≡↓|40, 1. |πThe value *1|εc|4α≡↓*444→α≠↓↑,|π↔ym¬qd
3707 awqxnxb a¬vckdd↔,succksthescjkkjrjfcks|ε)XivMi↓~↓i154*24*2Xuk2
3708 6))M))4≤↓466 [[qussxgqqpvmfsmxfhhysfxgvm Q*2xIvm|7(*2I6cNg2|cm
3710 |6α"↓|4r|gα_↓|g2|im. |πOther values of |εc |πdo
3716 not seem tonpaadftomsuvvlwscjwwwivnfyppqsmmbF44\≥#,|[↓kffhhy
3718 yysym¬q∧fuwlpnbssuwpufkkcoory whdn used with
3722 suitable starting valqes.|''{{**}{I19H}}|≡**U≡↓4≡)]:*3577Ccppuw
3725 pqz)[]::Szh \εhI4C¬P|4π,nk|4|¬L|40.|'{A3}*?*?*?|π|≡A|≡2|≡.|9|1[
3727 |εn|4α=↓|41?]|9|πIf |εn|4α=↓|41, |πthe algorithm
3731 terminates.|'{A3}|≡A|≡3|≡.|9|1[Divide.]|9Set
3733 |εq|4|¬L|4|"ln/d|βk|"L, rN4←¬L|4,N44[.mdF44\≤Fβk*2.(([[yjjs|\
3734 ≥q|[≤kff|≥≤c|[≤jjshhysqq¬opufmhundfrdx¬unfdrnobbauned
3735 wyen |εn |πis divided by |ε-Sβk))|'{A3d|π|≡A|≡4|≡.|9|1[Zero
3742 remainder?]|9If |εr|4|=|↔6α=↓|40, |πgo to step
3747 A6.|'{A3}|≡A|≡5|≡.|9|1[Factor found.]|9Increase
3750 |εt |πby 1, set |ε≥|βt|4|¬{|4d|βk↔,|πset |εn|4|¬L|4≥)
3756 |πReturn to step A↑.|'{A↓d c≡UN≡6N*2.|9|3[Gow
3762 qkotient?]|9If |εq|4|¬Q|4d|βk, |πincrease |εk
3766 |πby 1λand rjzqjnntonsyzqpU↓#[]↓{↓} **≡U**7***2.::57[\*2n|πis
3770 prcvx)[]::55Cccjauss \εh|[~xy∀7,sszh P≥p|lhI4M¬L|4n,
3773 Nπknd !|9|4|1|1|1As an example of Algorithm A,
3780 consider the factorization of the number |εN|4α=↓|425852.
3787 |πWe immediately _nd that |εN|4α=↓|42|4|¬O|412926;
3792 |πhence |εp|β1|4α=↓|42. |πFurthermore, 12926|4α=↓|42|4|¬O|46
3795 463, so |εp|β2|4α=↓|42. |πBut now |εn|4α=↓|46463
3801 |πis not divisible by 2, 3, 5,|4.|4.|4.|4,|419;
3808 |πwe _nd that |εn|4α=↓|423|4|¬O|4281, |πhence
3813 |εp|β3|4α=↓|423. |πFinally 281|4α=↓|412|4|¬O|423|4α+↓|45
3816 and 12|4|¬E|423;λhence |εp|β4|4α=↓|4281. |πThis
3820 determination of the factors of 25952 requiress12
3827 division opejazions; on the other hand, if we
3835 had tried to factor thesswigvtlqssxjwlajcnuxxbj
3840 2584\?(whicm is prime), at least 38 division
3847 operations would bdsnecessajx),Thiusipluuygjwessthysfjcohhha
3849 z AwgorithmnA requurds a running timesroughly
3855 proportionawitonmj¬(*4≥≥PilHi↓_↓|β1/]44}}|v7∀PilH)*45*2)|[/kfqw
3855 ssszh|≥≥Pi1→4*245#[,]["!|::44555555[πHysssqqufcks
3856 Q≤fIl[,ff|β3,nd|r2,|4.|4.|4. |πof trial divisors
3860 usedsin AwggrithmnUucjknxbshwkkfnhomxbssuvvpqy/6,7,
3862 5, 7*?*? be taken to be simply 2, 3, 5, 7, 11,
3875 13, 17, 19, 23, 25, 29, 31, 35,|4.|4.|4.|4, where
3884 we alternately add 2 and 4 after the _rst three
3894 terms. This sequence contains all numbers which
3901 are not multiples of 2 or 3; it also includes
3911 numbers such as 25, 35, 49, etc., which are not
3921 prime, but the algorithm will still give the
3929 correct answer. A further savings of 20 percent
3937 in computation time can be made by removing the
3946 numbers |ε30m|4|¬N|45 |πfrom the list for |εm|4|¬R|41,
3953 |πthereby eliminating all of the spurious multiples
3960 of 5. The exclusion of multiples of 7 shortens
3969 the list by 14 percent more, etc. A compact bit
3979 table can be used to govern the choice of trial
3989 dcvvsors.],'!|9|4|1←1|1Iff|εN |π∪uskfo∧knhombdssxawl#,iphius
3990 cjauxmk∧∧wshonhq¬ksuuhw∧∧asmffawlphhysnfkkssuj¬sprcvdssas
3991 pajg offhhysprggrj¬.,Fbrcsxk¬vpa↔,ikf|≥n|π/uspwsssthqknuumcl
3992 livn,,wwsnfedf *2-onvqyiccvqkdshhys56**?pccvxsspwssshhqknuuhhm
3993 ¬uukff()xglg∧wdfxxyhhysv¬wqus|≥≠Fβ15β66i%*34*245100λ|["onhzjvc
3993 ckwzshhysppuyhicnckuss|\*2n|[7usuupvcvxspwjg∧jchhqkn:97V∩).SU
3993 kvhuuhw∧∧wsckknxbssszhuqpxxymxakfsmxfuusymgghuu¬¬ppuj¬ypvggg
3993 rβ¬.,qqpcvhx¬up∧fs hhshw∧∧lsnjush jfter thenfjctoring
3997 program has been loaded into thescompuzej*2?ssesUWgggcphmm577
4002 7777,qqpcvhiuscjqvccmzdficnUQpqffk¬xu**,mgcssessxxjccuss?(.N,
4002 N'*?{H9L11}|≡F|≡i|≡g|≡. |≡1|≡1|≡.|9|4Probability
4004 distribution functions for the two largest prime
4011 factors of a random integer |¬E|εx.|;|'{H10L12}|π|≡F|≡e|≡r|≡
4018 m|≡a|≡t|≡'|≡s |≡m|≡e|≡t|≡h|≡o|≡d|≡.|9|4Another
4020 approach to the factoring problem, which was
4027 used by Pierre de Fermat in 1643, is more suited
4037 to _nding large factors than small ones. [Fermat's
4045 description of his method, translated into English,
4052 appears in L. E. Dickson's |εHistory of the Theory
4061 of Numbers |π|≡1 (New York: Chelsea, 1952), 357.]|'
4069 !|9*34←1←155*5usuxdsthat |εN|4α=↓|4uv, |πwhere
4072 |εu|4|¬E|4v. |πFor practical purposes we may
4078 assume that |εN |πissodd)?thissmdaffsthat |εu
4083 |π_fd |ε*2n|πalso are odd. We can therefore let|'
4091 ↓J6}|εx|4↓≡↓**4=S4↓~↓*44#)/2,`!yS4≡↓|4(*2V4≠↓←4=)≡2,←JD(↓1*2*4;{A
4091 4}¬|ε|4α=↓**4x|g2|4α_↓|4y|g2/$!0|4←¬JS4≥S44¬{S4)F44¬DS4].[KJ(
4091 ↓2)*3;J**}|π'Fermat's met*?*?*?Fermat's method consists
4095 of searching for values of |εx |πand |εy |πthat
4104 satisfy this equation; the following algorithm
4110 shows how factoring can therefore be done |εwithout
4118 using any division|*/:|\|'{A3}|π|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m
4122 |≡C (|εFactoring by addition and subtraction).|9|πGiven
4128 an odd number |εN, |πthis algorithm determines
4135 the largest factor of |εN |πless than or equal
4144 to |ε|¬H|v4N|)|1.|'{A3}{I1.9H}|π|≡C|≡1|≡.|9|1[Initialize.]|9
4146 Set |εx|¬S|4|¬L|42|"l|¬H|v4N|)|"L|4α+↓|41, y|¬S|4|¬L|41,
4149 r|4|¬L|4|"l|¬H|v4N|)|1|"L|g2|4α_↓|4N. |π(During
4151 this algorithm |εx|¬S, y|¬S, r |πcorrespond respectively
4158 to |ε2x|4α+↓|41, 2y|4α+↓|41, x|g2|4α_↓|4y|g2|4α_↓|4N
4162 |πas we search for a solution to (12); we will
4172 have |ε|¬Gr|¬G|4|¬W|4x|¬S |πand |εy|¬S|4|¬W|4x|¬S.)|'
4176 {A3}|π|≡6N≡2←≡)]9*31[πext |εr.]←9←πIf |ε⊃N4←¬E|41,,gonto
4179 steq C6.←'{J↓¬|π|≡**|≡3|≡)]9|1[Step |εy.]←9*3π*3et
4182 |εr|4|¬G|4⊃|4α_↓*44;S¬F↔,yS¬KS4←¬L|4≥Y¬FS4~↓]42/,|[≤kffcjzqkc
4182 nhomC67[,↓{↓¬|≡**C****4≡*2]9:17*4bnd?*4]9*/kf|\≤C4↓≡↓**45,,|["hysawg
4182 grcphmmhzrmvnjtzs;hwe have|'{J6}|εN|4α=↓*34()F¬KS4α≠↓**4≥S¬S)≡
4184 2)(()X¬KS4α~↓4≥Y¬FS4α≠↓M46*2≡2)↔];{6}!!|1←5←π≠kdf((≥*2F¬KS4≤↓*4
4184 4;S¬K)≡2/|π#ushhyslwjgjsz fjktorcmxf|ε**n|[∩wssshhuknmgcsqquw
4185 phom|≥\¬}Hv76N)(57[]↓{↓¬*2|[[≡**C≡4≡*2[9*317*3zeq
4186 |εx)]]:*3[*4sz |ε≠C44¬}P46C4α↓4X}}↔,xX¬}S44}}P4X}}S4α↓466,|[↓k
4187 ffcjzqkcnhomC77.N,N≤}CC}!|9|4|1|1|11he readdjcmay
4189 efk∧xs_,ducvchhysfaktorksof 377/xxshqkffuuucvvhhpusuwgggcphm
4190 ..hHysnk¬mbjcnxfssteps to _nd the factors |εu,
4196 v |πof |εN|4α=↓|4uv |πis essentially proportional
4202 to |ε)F¬SS4α~↓**4\Y}}S4↓↓46*2664↓↓44[∩p}¬HVv4*/*2NN)|1N"L|4α=↓|4
4203 v|4α_↓|4|"l|¬H|v4N|)|1|"L; |πthis can, of cokrse,,bdsuuvjj¬s
4207 pwjg∧snk¬xbj/,uwlhm¬¬vhsakvh yzqickknnbsfbmfsvvjcycrupcdly
4209 on most computers. An improvement whicv rdquiressmngys|≥↓(*4N
4215 v35V/6g3*2)|[πvujjwpvmfsicnhhysq∧gkyhckuss husnbef{U0}{H10L12
folio 488 galley 7
4216 M29}|πW58320#Computer Programming!ch. 4!f. 488!g.
4220 7|'{A6}|π!|9|4|1|1|1It is not quite correct to
4227 call Algorithm C ``Fermat's method''; in spite
4234 of the fact that the main loop is quite fast
4244 on computers, it is not very suitable for hand
4253 calculation. Fermat actually did not keep the
4260 running value of |εy; |πhe would look at |εx|g2|4α_↓|4N
4269 |πand tell whether or not this quantity was a
4278 perfect squard by lookingcaz itsspwaszhsugnc_cjnt
4283 digits. (The last two digits of a perfect square
4292 must be 00, |εa1, a4, 25,,b,n|πogc|≥ε*5),|[≤qyjjs|≥εu|[#u
4298 unneven digit and |εb |πis an odd digit.) Therefore
4307 he avoided the operations of steps C2 and C3,
4316 replacing them by an occasional determination
4322 that a certain number is not a perfect square.|'
4331 !|9|4|1|1|1Fermat's method of looking at the
4337 rightmost digits can, of course, be generalized
4344 by using other moduli. Suppose for clarity that
4352 |εN|4α=↓|411111, |πand consider the following
4357 table:|'{H9L11}|∪!!|9|1|1|1|∂!!!!!!!!!!!!|∂!!!!!!!!!!!!|∂!!!
4358 !!!!!!!!!|∂|E|'|>|εm|'|πif |εx |πmod |εm |πis|'
4366 then |εx|g2 mod |εm |πis|'and (|εx|g2|4α_↓|4N)
4373 |πmod |εm |πis|'>|>|9|13|'0,|41,|42|'0,]41,|41|'
4381 1,|42,|42,|'>|>|9|15|'0,|41,|42,|43,|44|'0,|41,|44,|44,|41|'
4387 4,|40,|43,|43,|40|'>|>|9|17|'0,|41,|42,|43,|44,|45,|46|'
4392 0,|41,|44,|42,|42,|44,|41|'5,|46,|42,|40,|40,|42,|46|'
4394 >|>|9|18|'0,←41,|42,|43,|44,|45,|46,|47|'0,|41,|44,|41,|40,|
4398 41,|44,|41|'1,|42,|45,N46,N41,|42,|45.N42N,2∂|>
4400 11|'0,N41,|42,]43,]44,]45#]46,]47#]4*/↔]4\)]451→]"[,45#]44/,I
4401 5(,|57,47#,47#,I5#,I\),44/,I55N"1[,I5[,|63,|4<,|46,|42,|42,|
4401 44,|48,|43,|||||||||||||||||||||||||||||||||||||||||||||||||
4401 ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4401 ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4401 ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4401 ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4401 ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4401 ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4401 ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4401 |||||||||| eeeeee*?*?*?*?|>11|'0,|41,|42,|43,|44,|45,|46,|4
4408 7,|48,|49,|410|'0,|41,|44,|49,|45,|43,|43,|45,|49,|44,|41|'
4410 10,|40,|43,|48,|44,|46/]42,]44/]48↔]47#]45→,2|'
4411 {H10L12}{IC}If |εx|g2|4α_↓|4N |πis to be a perfect
4418 square |εy|g2, |πit must have a residue mod|4|εm
4426 |πconsistent If |εx|g2|4α_↓|4N |πis to be a perfect
4434 square |εy|g2, |πit must have a residue mod|4|εm
4442 |πconsistent with this fact, for all |εm. |πFor
4450 example, if |εx|4|πmod|43|4|=|↔6α=↓|40, then
4454 for |εN|4α=↓|411111, |ε(x|g2|4α_↓|4N)|4|πmod|43|4α=↓|42,
4457 so |εx|g2|4α_↓|4N |πcannot be a perfect square;
4464 therefore |εx |πmust be a multiple of 3 whenever
4473 11111|4α=↓|4x|g2|4α_↓|4y|g2. |πThe table tells
4477 us that|'{A6}|h|∂|εx |πmod 11|4α=↓|40 or 4 (hence
4485 |εx |πmod 4|4α=↓|40);|E|n|;|L|εx |πmod 3|9|1|4α=↓|40;>
4491 |L|εx |πmod 5|9|1|4α=↓|40, 1, or 4;>|L|εx |πmod
4499 7←9|1|4α=↓←42, 3, 4, or 5;>|L|εx |πmod 8|9|1|4α=↓|40
4507 or 4 (hence |εx |πmod 4|4α=↓|40);>|L|εx |πmod
4515 11|4α=↓|41, 2, 4, 7, 9, or 10.>{A6}This narrowssfb∧n
4524 thessearch for |εx |πconsiderably. For example,
4530 |εx |πmust be a multiple of 12. We musz have
4540 |εx|4|¬R|4|"l|¬H|v4N|)|1|"L|4α=↓|4106, |πand
4542 it is easy to verify that the _rst value of |εx|4|¬R|4106
4553 |πwhich satis_es all of the conditions in (13)
4561 is |εx|4α=↓|4144. |πNow 144|g2|4α_↓|411111|4α=↓|49625,
4565 and by taking the square root of 9625, we _nd
4575 it is not a square. The _rst vawue of |εx|4|¬Q|4144
4585 |πwyich satis_es (13) is |εxF4α=↓|4156. |πIn
4591 this case 156|g2|4α_↓|411111|4α=↓*4413225←4α=↓|4114|g2;
4594 |πsonwe have the ddsuredfsxgqtionn|εx|4α=↓|4156,
4598 y|4α=↓|4115. |πThis calculation shows that 11111|4α=↓|441|4|
4603 ¬O|4271. The hand calculations involved in this
4610 example are comparable to the amount of work
4618 required to divide 11111 by 13, 17, 19↔ 23, 29,
4628 31, 37, and 41, even though the factors 41 and
4638 271 are not very cgose to each other; thus we
4648 can see the advanoa∧ds of Fdjmat'↔smezhod.]''!|9|445H1←15cnp
4653 lakesoxfthesmodkwi confuderedficn(↓3)↔qascjfnuuesakxypg∧ejfs
4654 offdkutincohpgcmxs) For example,λif we had used
4660 25 in place of 5, we would _nd that the pofsubgesvalues
4671 ofs|εy|g2|4←πmod|427 are only permissuble values
4676 of |ε) |πmodf25λajjs→,,5/,6/,51[,55#,5*5),ukff63..Hhpusvvvxss
4678 mmgjsicfxgv¬wpvmnhhqnn(*2).Icngjffjjw/,qaswqplpv∧zhmmgjsicfxg
4678 v¬wpvmnmmbkqgm|≥≥PV36|["hqknmmbkqgm|\≥#,|[(xgcmbdfpvcvxss|\≥
4678 #,|[≤qyfn|≥*2XV364↓↓46N44."M45→(([[mbkqgm \≥*2)|[[qusuusxgqqpc
4679 mn I≤x.N'!|9|4|1←5555[πhssmmbkqwjcmxzhmbfkkuyhuusdfiusccwlwd
4680 fuu |εsidve procedure, |πsince we can imagine
4687 passing all inte∧ers |ε*2f|π"hrg¬¬vhau``*4uu¬¬-',fxgcqqpcvhmmv
4690 qyhhmxssv¬wqussqqith |≤x Nπmod 3|4α=↓|40 |πcome
4695 out, then sifting these numbdjksthrgk¬vhukmohyjcsuu¬¬sqwhen
4700 we sieve with respect to moduli which are relatively
4709 prime in pairs, each sieve is independent of
4717 the others because of the Chinese Remainder Theorem
4725 (Theorem 4.3.2C). So if we sieve with respect
4733 to, say, 30 di=erent primes, only about one value
4742 in every 2|g3|g0 will need to be examined to
4751 see if |εx|g2|4α_↓|4N |πis a perfect square |εy|g2.|'
4759 |'|π|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m |≡D |ε(Factoring
4763 with sieves).|9|πGiven an odd number |εN, |πthis
4770 algorithm determines the largest facgor of |εn
4777 |πless than or equal to |¬H|v4|εN|)|1. |πThe
4784 procedure uses moduli |εm|β1, m|β2,|4.|4.|4.|4,
4789 m|βr, |πwhich are relatively prime to each other
4797 in pairs and relatively prime to |εn. |πWe assume
4806 that |εr |π``sieve tables'' |εS[i,N4j] |πfor
4812 |ε0|4|¬E|4j|4|¬{|4m|βi,n1|4|¬E|4i|4|¬E|4r, |πhave
4814 been prepajed, where|'{A6}|εS[i,|4j]|4α=↓|4|↔A|(1,!!|πif!!|ε
4817 j|g2←4α_↓|4N|4|"o|4y|g2 (|πmodulo |εm|βi)n|π.as
4820 a solution |εy;|d50,|)|;{A6}{I1.10→}d|π|≡D|≡1|≡.|9|1[Initial
4823 ize.]|9Set |εxX44¬L|4|"#|¬H|v4N|)|1|"P, |πand
4826 |εk|βi|4|¬L|4(|→α_↓x) mod |εm|βi |πfor |ε1|4|¬E|4i|4|¬E|4r.
4831 (|πThroughout this algorithm the index variables
4837 |εk|β1, k|β2,|4.|4.|4.|4, k|βr |πwill be set
4843 so that |ε(|→α_↓x) |πmod |εm|βi|4α=↓|4k|βi.)|'
4848 {A3}|π|≡D|≡2|≡.|9|1[Sieve.]|9If |εS[i,|4k|βi)|4α≡↓|41λ|πfor
4850 |ε*5←4|¬E|4∪|4|¬ES4⊃,,|π∩o tonszeq D**#['↓J3}|≡D|≡3|≡.|9|1[Ste
4852 p |εx.]]9Set |εx|4|¬L|4)|4α"↓*441,λ|[≤fd |ε*2Kβi|4←¬}P4(k|βiI4
4855 α_↓*441*2n|πmod |εm|βi |πfor |ε1|4|¬E|4i|4|¬E|4r,
4859 |πand return tonsteppnD2.|]N'''''''''''*?*?*?and
4862 return to step D2.|'{A3}|≡D|≡4|≡.|9|1[Test |εx|g2|4α_↓|4N.]|
4867 9|πSet |εy|4|¬L|4|"l|¬H|v4x|g2|4α_↓|4N|)|1|"L
4869 |πor to |ε|"l|¬H|v4x|g2|4α_↓|4N|)|1|"L. |πIf
4873 |εy|g2|4α=↓|4x|g2|4α_↓|4N, |πthen |ε(x|4α_↓|4y)
4876 |πis the desired factor, and the algorithm terminates.
4884 Otherwise return to step D3.|'|'{IC}{H10L12}{IC}!|9|4|1|1|1T
4890 here are several ways to make this procedure
4898 run fast. For example, we have seen that if |εN
4908 |πmod 3|4α=↓|42, |πthen |εx |πmust be a multiple
4916 of 3; we can set |εx|4α=↓|43x|¬S, |πand use a
4925 di=erent sieve corresponding to |εx|¬S, |πincreasing
4931 the speed by a factor of 3. If |εN |πmod 3|4α=↓|41,
4942 |εx |πmust be congruent to |→|¬N (modulo 9),
4950 sb we cjf rkfntwb sue¬ess(↔or |≥)F¬F |πafdn|εx|¬C,
4957 |πεhere |εx|4α=↓|49)|¬S|4α+↓|41 |π_nd |ε)S4α=↓|49)|¬C|4α≠↓|4
4960 1)↔|πto increase thesspeedfby a factor of 4|f1|d32|).
4967 If |ε] |π.mbf444α≡43#,|["hefn|≥*2x|[.¬uyhxb aumkqlippe
4971 off4λand the speed is increased by an additionaw
4979 factor of 4; in the other case, when |εxs|πmod
4988 4|4α=↓|41, |εx |πmust be odd so the speedfmjysbdsdbk∧∧ed.
4996 Anoohejnway tondouble the speed of the algorithm
5003 (at the expensesoffstora∧jsspacj)↔iushoncombicfspairssmf
5006 moduli, using |εm|βr|βα_↓|βkm|βk |πccnppace oxf|≥*2Mβkk|[(xgc
5010 |≥*5544¬{U4≡K44}}Q44F4f↓36)*2#[,'!|:Y44555414[↓kns¬dfnmmgjsivp
5010 vrgwkmhmxzhmbfmxfsqqedkcvvuqpUWgggcphmmCciushomuusshhys]`αBo
5010 gwaknmvqjjwpvmf↔',fb¬kffmmnmmxyhxknaj¬ycvmvuqzjk).Paz
5011 uusuusu¬xsfxgcsx¬¬vpwshhqwh|¬¬M¬¬I¬¬xiusuuxkckj¬ycgmvqqzjcqq
5011 phh73∞x¬pysper word. The tables |εS[i,|4k|βi]
5016 |πcan be kept in memorx wuth one b¬phper enor¬;?thuss3πλvalu
5024 es can bdsszoredficna sucvgasword),The opejjzion
5029 |¬a|¬fN¬d↔λwhicm rdqlacdssthe |≥kFπ"hhxkt offthesakckxkwawor
5032 nbxszejo iffhhes|ε≡K["h but offuusqekc=_dfwbrjfin
5036 mxxmgx isszejo,,fbrn|ε1←4|¬E|4k|4|¬ES430, |πcan
5039 be ussdftonpvgcdsss73λv¬wuassmxf|≥*2x|[≤z omck*3?Forncvnvdfcuf
5041 cd↔,qwscjknm¬kksse¬jjjwicopiassoffthystab∧wss|ε*3[/,]4≡**,|π↔b
5041 nhhuz thestab∧essfmrcessfxgc|≥*2Nβii|[/nvogvjslcm(|ε)Nβi,|43π
5042 )↔|πbits;?thefnhhessuu¬¬sta∧∧wssfxrnsakv modkwuus=εliuknicmz
5043 ∧gjwink¬xbjcmxfq∧gjf).Ukfdjchhysssuusu¬vppvmf↔,73∞sxxkkqpvmf
5043 smxfhhysm¬ucnpgovpicnAwgggcthmnFfujj equuvaleft
5045 to code of the following form:|'|'{H9L11|h|∂4¬d|¬↑2|∂←¬j|¬3←
5052 ¬n|¬n∨|∂|¬s|¬1|¬,!!|∂If|4rI1|4|¬W|40,|4set|4rI1←4|¬L|4rI1|4α
5052 +↓|4lcm(|εm|β1,|422).←E|n|;|L|π|¬d|¬2|L|¬l|¬d|¬1|L|¬k|¬1←LrI
5053 1←4←¬{|4←ε≡F=|β1|¬S.>|L|L|π|¬l|¬d|¬aUL|¬sS¬↓4¬↔]¬↓4PrJU4←¬}P
5054 44≥\S¬}(77]44[3C57[7∂|PPPP¬¬F¬¬S¬¬C¬5P|¬↓←LrC1|4|¬{I4rC1←4↓≠
5054 ↓|41.2⊗|L|L|¬jF¬4¬n|¬nNL{J1}α/↓|≤%|¬2>|L|L|¬i|¬n|¬c|¬1|L|¬m|
5055 ¬1|LIf|4rI1|4|¬W|40,|4set|4rI1|4|¬L|4rI1|4α+↓|4lcm(|εm|β1,|4
5055 30).>|L|L|π|¬sS¬t|¬1|L|¬k|¬1←L|εk|=|β1|¬S|4←¬W|4|πrI1.>
5057 |L|L|¬l|¬dF¬1|L|¬k|¬2|LrI1|4|¬L|4|εk|=|β2|¬S.>
5058 |L|L|π|¬a|¬kN¬d|L|¬f|¬2|¬,|¬1←LrA|4|¬{|4rA|42`≠fd'']44\*/S¬F(
5058 7/]44π⊃C57.6∂|PPPI¬¬F¬kS}¬C¬|L|¬↓4LrC5444}}P4/C544≤↓45#7>
5059 |L|L|¬¬K¬↓←¬kN¬¬NP{J↓*2***2↑*/¬↑2∂|PIPI¬c|¬nN¬kC¬4LI¬¬N¬6PIfF4/C
5059 554|¬{Q45.]4?szH4/C5544¬}P46C554~↓4∀vv)(≥*2Mi2/,473))7>
5060 PPPPM[}¬s}¬hN¬5|PV¬kN¬2|L|*2k|=|β2N¬S|4|¬L|4|πrI1.>
5062 |PIP7[47[4#7>|PPPP¬¬S¬¬H}*25PP}}K}¬CPP\*2k*/*/IrC}}S44}}P44[3C57
5063 7>|L|L|¬i|¬n|¬c|*?{U0}{H10L12M29}|πW58320#Computer
folio 492 galley 8
5065 Programming!ch. 4!f. 492!g. 8|'{A6}!|9|4|1|1|1If
5070 the table entries for |εm|βi |πdo not come out
5079 to be an integral number of words, further shifting
5088 of the table entries would be necessary on each
5097 iteration so that the bits are aligned properly.
5105 This would add quite a lot of coding to the main
5116 loop and it would probably make the program too
5125 slow to compete with Algorithm C unless |εv/u|4|¬E|4100
5133 |π(see exercise 7).|'!|9|4|1|1|1Sieve procedures
5138 can be applied to a variety of other problems,
5147 not necessarily having much to do with arithmetic;
5155 a survey of these techniques has been prepared
5163 by Marvin C. Wunderlich, |εJACM |π|≡1|≡4 (1967),
5170 10<19.|'!|9|4|1|1|1Special sieve machines (of
5175 reasonably low cost) have been constructed by
5182 D. H. Lehmer and his associates over a period
5191 of many years; see for example |εAMM |π|≡4|≡0
5199 (1933), 401<406. |πLehmer's electronic delay-line
5204 sieve which began operating in 1965 processes
5211 one millivmnnumbers per second; thus, each iteration
5218 of the loop in Algorithm D can be performed in
5228 one mvccgxecond on this device. Another way to
5236 factor sieves is described by D. H. and Emma
5245 Lehmer in |εMath. Comp. |π|≡2|≡8 (1974), 625<635.|'
5252 |'|≡T|≡e|≡s|≡t|≡i|≡n|≡g |≡f|≡o|≡r |≡p|≡r|≡i|≡m|≡a|≡l|≡i|≡t|≡
5255 y|≡.|9|4None of the algorithms we have discussed
5262 so far is an e∃cient way to determine that a
5272 large number |εn |πis prime. Fortunately, there
5279 are other methods available for settling thiusquestion;
5286 e∃cient methods for this purpose have been devised
5294 by |=⊂E. Lucas and others, notably D. H. Lehmer
5303 [see |εBulletin Amer. Mazh. Soc.λ|π|≡3|≡3 (1927),
5309 327<340].|'!|9|4|1←1|1According to Fermat's theorem
5314 (Theorem 1.2.4F)↔λ|εx|gp|gα_↓|g1 |πmod |εp|4α=↓|41λ|πif
5318 |εp |πis prime and if |εx |πcs noo asmultiple
5327 of |ε≥#.|πFurthermore, there are e∃cient ways
5333 to calculate |εx|gn|gα_↓|g1 |πmod |εn, |πrequiring
5339 only |εO(|πlog|4|εn) |πoperations of multiplication
5344 mod |εn. |π(We shall study these in Section 4.6.3
5353 below.) Therefore we can often determine that
5360 |εn |πis |εnot |πprime when this relationship
5367 fails.|'!|9|4|1|1|1For example, Fejrmat vvvvvvv*?*?*?*?!|9|4|1|1
5371 |1For example, Fermat veri_ed that the numbers
5378 2|g1|4α+↓|41, 2|g2|4α+↓|41, 2|g4|4α+↓|41, 2|g8|4α+↓|41,
5382 and 2|g1|g6|4α+↓|41 are prime. In a letter to
5390 Mersenne written in 1640, Fermat conjectured
5396 that |ε2|g2|in|4α+↓|41 |πis always prime, but
5402 said he was unable to determine de_nitely whether
5410 4294967297|4α=↓|42|g3|g2|4α+↓|41 |πis a prime
5414 or not. We can compute 3|g2|i3|i2 mod (2|g3|g2|4α+↓|41)
5422 by using 32 operations of squaring a number modulo
5431 2|g3|g2|4α+↓|41, and the answer is 3029026160;
5437 therefore (by Fermat's own theorem, which he
5444 discovered in the same year 1640*3) we know that
5453 2|g3|g2|4α+↓|41 is |εnot |πprime. This argument
5459 giv¬ssus absolutely no idea what the factors
5466 are, but it answers Fermat's question.|'!|9|4|1|1|1Fermat's
5473 theorem is a powerful test for showing that |εn
5482 |πis not a prime. When |εn |πis not prime, it
5492 is always possible to _nd a value of |εx|4|¬W|4n
5501 |πsuch that |εx|gn|gα_↓|g1 |πmod |εn|4|=|↔6α=↓|41;
5506 |πexperience shows that in fact such a value
5514 can almost always be found very quickly. There
5522 are some rare values of |εn |πfor which |εx|ε|gn|gα_↓|g1
5531 |πmod |εn |πis frequently equal to unity, but
5539 then |εn |πhas a factor less than |=|g3|¬H|v4|εn|)|1;
5547 |πsee exercise 9. One example is |εn|4α=↓|43|4|¬O|411|4|¬O|4
5553 17|4α=↓|4561; |πhere |ε|≤l(n)|4α=↓|44[lcm(2,|410,|416)|4α=↓|
5555 480 in the notation of Eq. 3.2.1.2<9, so |εx|g8|g0
5564 |πmod 561|4α=↓|41|4α=↓|4|εx|g5|g6|g0 |πmod 561
5568 whenever |εx |πis relatively prime to 561.|'!|9|4|1|1|1The
5576 same method can be extended to prove that a large
5586 prime number |εn |πreally |πis |πa prime, by
5594 using the followingnikda: |ε|πusingnthe folllowinnusing
5599 the following idea: |ε|πusing the following idea:
5606 |εIf there is a number x for which the order
5616 of x modulo n is equal to |εn|4α_↓|41, then n
5626 is prime. |π(The order of |εx |πmodulo |εn |πis
5635 the smallest positive integer |εk |πsuch that
5642 |εx|gk |πmod |εn|4α=↓|41; |πsee Section 3.2.1.2.)
5648 For this condition implies that the numbers |εx|gk|4|πmod|4|
5655 εn |πfor |ε1|4|¬E|4k|4|¬E|4n|4α_↓|41 |πare distinct
5660 and relatively prime to |εn, |πso they must be
5669 the numbers 1, 2,|4.|4.|4.|4, n|4α_↓|41 |πin
5675 some order; thus |εn |πhas no proper divisors.
5683 If |εn |πis prime, such a number |εx (|πa ``primitive
5693 root'' of |εn) |πwill always exist; see exercise
5701 3.2.1.2<16. In fact, the number of such primitive
5709 roots is rather numerous; there are |ε|≤'(n|4α_↓|41)
5716 |πof them.,ukff|εn/←≤-(n|4α_↓|41)|4α=↓|4O(|πlog|4log|4|ε≡).|
5717 '!|9|4|1|1|1|ε|πIt is unnecessary to calculate
5723 |εx|gk|4|πmod|4|εn |πfor all |εk|4|¬E|4n|4α_↓|41
5727 |πto determine ifnthe order of |εx |πis |εn|4α_↓|41
5735 |πor not. The order of |εx |πwill be |εn|4α_↓|41
5744 |πif and only if|'{A6}|ε!|9|4|1|1←1|4|1|πi)|9|εx|gn|gα_↓|g1|
5748 4|πmod|4|ε↔|4α=↓|414'!|9|4|1|1←1←π∪i)|9←ε)Fg(*4gn|gα_↓|g1|g*2(
5748 v/|gp|4|πmod|4|εn|4|=|↔6α=↓|41 |πfor all primes
5752 |εp |πwhich divide |εn|4α_↓|41.|'{A6}Nπ*1Fbr |εx|gkS4←π.odF4←
5757 ε,N4α=↓|41λ|πif afd onlysif |εs |π∪s a multiple
5764 of the order of |εx |πmodulo |εn. |πIf the two
5774 conditions hold, andfif |εk |πis the order of
5782 |εx |πmodulo |εn, |πwe therefore know that |εk
5790 |πis a divisor of |εn|4α_↓|41, |πbut not a divisor
5799 of |ε(n|4α_↓|41)/p |πfor any prime factor |εp
5806 |πof |εn|4α_↓|41; |πso |εk |πmust be equal to
5814 |εn|4α_↓|41. |πThis completes the prooffhhat
5819 conditions (i) and (ii) su∃ce to establish the
5827 prcmjlity ofn|εn.|'|π!|9|4|1|1|1Exercise 10 shows
5832 that we may in fact use di=erent values of |εx
5842 |πfor each prime |εp, |πand |εn |πwill still
5850 be prime. We may restrict consideration to primes
5858 |εx, |πsince the order of |εuv |πmodulo |εn |πdivides
5867 the least common multiple of the orders of |εu
5876 |πand |εv |πby exercise 3.2.1.2<15. Conditions
5882 (i) and (ii) can be tested e∃ciently by using
5891 the rapid methods for evaluating powers oxfiunumbercdiscusse
5897 d in Section 4.6.3. But it is necessary to know
5907 the prime factors of |εn|4α_↓|41, |πso we have
5915 an interesting situation in which the factorization
5922 of |εn |πdepends on that of |εn|4α_↓|41*3|'|π|≡A|≡n
5930 |≡e|≡x|≡a|≡m|≡p|≡l|≡e|≡.|9|4The study of a reasonably
5935 typical large factorczation will help to _x the
5943 ideas we have discussed so fjr. Lez uustryston=≡dfthespccmes
5950 fkkgorksoff26v36g3|g6←4α+↓|41. The factorization
5953 of this 65-digit number can be initiated by noticingv
5962 t*?*?*?*?t|]≤{K2|g2|g1|g4|4α+↓|41|4α=↓|4(2|g1|g0|g7|4α_↓|42|g5|g
5962 4|4α+↓|41)(2|g1|g0|g7|4α+↓|42|g5|g4|4α+↓|41);|J!(14)|;
5963 {A6}|πthis identity is a special case of some
5971 factorizations discovered by A. Aurifeuille in
5977 1873 [see Dickson's |εHistory, |π|≡1, p. 383].
5984 We may now examine each of the 33-digit factorfsin
5993 (14).]'!|9|4|1|1|1A computer program readily
5997 discovers that 2|g1|gπ←g7|4α_↓|42←g5←g4|4α+↓|41|4α=↓|45|4|¬O
5999 |4857|4|¬O|4|εn|β0, |πwhere|'{A6}|εn|β0|4α=↓←4378**6899961660
6001 0577662392733α6J∨(35)N;{J6}Sπ⊗is a 29-digit numberchaving
6005 no prime factors lesssthafn1000. A multiple-*2recision
6011 calculation using thes``binary method''λof Section
6016 4.6.3 syo∧s thawh|'{A6}|*?*?*?ε3|gn|r0|gα_↓|g1|4|πmod|4|εn|β0|4
6019 α=↓|41,|;{A6}|πso we suspect that |εn|β0 |πis
6026 prime. It is certainly out of the question to
6035 prove that |εn|β0 |πis prime by trying the 10
6044 million million or so poteftial divisbgk↔nbkyhthesmxzhmdndis
6049 kkssedsa∧bve givessa feasub∧e test for primjwity:
6055 okj nexb goaw isstonfjkvorc|ε≡Ni1→4≤↓45#.|[↓qphhppptlwsfk≥*2k
6058 qly)naucgmputer program _↔ds that|'{A6}|εnNβ0|4α_↓*441|4α=↓|4
6062 2|4|¬O|42|4|¬O|419|4|¬O|4107|4|¬O|4353|4|¬O|4n|β1,!!n|β1|4α=
6062 ↓|41339127077551082260549*?*?*?*?Here |ε3|gn|r1|gα_↓|g1
6064 |πmod |εn|β1|4|=|↔6α=↓|41, |πso |εn|β1 |πis not
6070 prime; by continuing Algorithm A or Algorithm
6077 B we _nd |εn|β1|4α=↓|491813|4|¬O|4n|β2, n|β2|4α=↓|4143675413
6081 657196977. |πThis time |ε3|gn|r2|gα_↓|g1 |πmod
6086 |εn|β2|4α=↓|41, |πso we will try to prove that
6094 |εn|β2 |πis prime. This requires the factorization
6101 |εn|β2|4α_↓|41|4α=↓|42|4|¬O|42|4|¬O|42|4|¬O|42|4|¬O|43|4|¬O|
6101 43|4|¬O|4547|4|¬O|4n|β3, n|β3|4α=↓|41824032775457.
6103 |πSince |ε3|gn|r3|gα_↓|g1 |πmod |εn|β3|4|=|↔6α=↓|41,
6107 |πwe know that |εn|β3 |πis composite, and Algorithm
6115 A _nds that |εn|β3|4α=↓|41103|4|¬O|4n|β4, n|β4|4α=↓|41653701
6119 519. |πThe number |εn|β4 |πbehaves like a prime
6127 (i.e., |ε3|gn|r4|gα_↓|g1 |πmod |εn|β4|4α=↓|41),
6131 |πso we calculate|'{A6}|εn|β4|4α_↓|41|4α=↓|42|4|¬O|47|4|¬O|4
6134 19|4|¬O|423|4|¬O|4137|4|¬O|41973.|;{A6}|πThis
6136 is mokru≠st complete factorization; we are ready
6143 to backtrack to the previous subproblem, proving
6150 that |εn|β4 |πis prime)λThssfoglg∧qcvmvaluassajdsno∧
6154 comvuted,λakcordingnto the prgcedkjdsof exercise
6158 10:|'←'|∂$!|∂$!!!|∂$!!!!!!|∂>!!!!!|∂4SS;&|>|εx|;
6162 p|;x|ur(n|β4α_↓1)/p|)|)|4|πmod|4|εn|β4|;x|gn|r4|gα_↓|g1|4|πm
6164 od|4|εn|β4|;>|>2|;!|9|1|1|12|;1|;(1)|;>|>2|;!|9|1|1|17|;
6175 766408626|;(1)|;>|>2|;!|1|119|;332952683|;(1)|;
6183 >|>2|;!|1|123|;1154237810|;(1)|;>|>2|;|9|1137|;
6193 373782186|;(1)|;>|>2|;19777:490790919|;(1)|;>
6201 |>3|;!|9|1|1|12|;1|;(1)|;>|>5|;!|9|1|1|12|;1|;
6211 (1)|;>|>7|;!|9|1|1|12|;1653701518|;1|;>{A12}{H10L12}|π|π(Her
6219 e ``(1)'' means a result of 1 which needn't be
6229 computed since it can be deduced from previous
6237 calculations.) Thus |εn|β4 |πis prime, and |εn|β2|4α_↓|41
6244 |πhas been completely factored. A similar ckwculation
6251 shows that |εn|β2 |πis prime, and this complete
6259 factorization of |εn|β0|4α_↓|41 |π_nally shows
6264 [after still another calculation like (16)] that
6271 |εn|β0 |πis prime.|'!|9|4|1|1|1The next quantity
6277 to be factored is the other half of (14),|'{A6}|εn|β5←4α=↓|4
6286 2|g1|g0|g7|4α+↓|42|g5|g4|4α+↓|41.|;{A6}|πSince
6288 |ε3|gn|r5|gα_↓|g1|4|πmod|4|εn|β5|4|=|↔6α=↓|41,
6289 |πwe know that |εn|β5 |πis not prime, and Algorithm
6298 B shows that |εn|β5|4α=↓|4843589|4|¬O|4n|β6,
6302 n|β6|4α=↓|4192343993140277793096491917. |πUnfortunately,
6304 |ε3|gn|r6|gα_↓|g1 |πmod |εn|β6|4|=|↔6α=↓|41,
6307 |πso we are left with a 27-digit nonprime number.
6316 Continuing Algorithm B might well exhaust our
6323 patience (not our budget#nobody is paying for
6330 this, we're using idle time on a weekend). But
6339 the sieve method of Algorithm D will be able
6348 to crackk P*2Nβ6 |πinto its two factors.|'|Ha*?*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
6355
folio 496 galley 9
0 {U0}{H10L12M29}|πW58320#Computer|9Programming!ch.
1 4!f. 496!g. 9|'{A6}|≡I|≡m|≡p|≡r|≡o|≡v|≡e|≡d |≡p|≡r|≡i|≡m|≡a|
5 ≡l|≡i|≡t|≡y |≡t|≡e|≡s|≡t|≡s|≡.|9|4Since the above
9 procedure for proving that |εn |πis prime requires
17 the complete factorization of |εn|4α_↓|41, |πit
23 will bog down for large |εn. |πAnother technique,
31 which uses the factorization of |εn|4α+↓|41 |πinstead,
38 is described in exercise 15; if |εn|4α_↓|41 |πturns
46 out to be too hard, |εn|4α+↓|41 |πmight be easier.|'
55 !|9|4|1|1|1Signi_cant improvements have recently
59 been discovered. Brillhart, Lehmer, and Selfridge
65 [|εMath. Comp. |π|≡2|≡9 (1975), 620<647, exp.
71 Corollary 11] have developed aumethod which works
78 when |εn|4α_↓|41 |πand |εn|4α+↓|41 |πhave been
84 onlyspartiawly faktorjd(?Suqpvfss|\*2N4α_↓|41|4α=↓|4f|1|gα_↓r
85 |gα≠↓↔|[≤kff|≥*2N4~↓4554*24↔F5←gα+↓⊃|gα+↓, |πwhere
87 we know the complete factorization of |εf|1|gα_↓
94 |πand |εf|1|gα+↓, |πand we know that all factors
102 of |εr|gα_↓ |πand |εr|gα+↓ |πare |¬R|εb. |πIf
109 |εb|g3f|1|gα_↓f|1|gα+↓|4|πmax(|εf|1|gα_↓,|4f|1|gα+↓)
110 |πis greater than |ε2n, |πa small amount of additional
119 computation, described in their paper, will determine
126 whether or not |εn |πis prime. Therefore numbers
134 of up to 77∀digits can usually be tested for
143 primality in 2 or 3 seconds, simply by casting
152 out all prime factors |¬W30030 from |εn|4|¬9|41
159 [|πsee J. L. Selfridge andfM..C#.Qqkfdrlich,
164 |εProc. Fourth Manitoba Conf. Numej. Math. |π(194),
171 109<120]. |πThe partial factorizazion of other
177 quantities like |εn|g2|4|¬N|4n|4α+↓←41 |π_fd
181 |εnNg2|4α+↓**41λ|π/kknxbsuusdfton≡vvvgv¬shhissmxzhodnszpll
182 fkkghyjc[[..C#,Qqplpu¬f↔,|≥\vgc#nFkkbh Mancpoba
184 Conf)λNumer. Math. (1975), |πto appear].|'|π!|9|4|1|1|1In
190 practice, when |εn has no small prime factors
198 and |ε3|gn|gα_↓|g1|4|πmod|4←εn|4α=↓|41, |πit
201 has almost always tqkndd out that |εn |πis prime.n(One
210 of the raresexkdqtions is |ε,N4α=↓|4|f1|d37|)(2|g2|g<|4α≠↓|4
214 9)|4α≡↓]42375544¬}M4163<*5#) |π3jj¬sL#.MVplwjchqusicv¬sypv∧wz
215 dfhhpusppyfmmxfmm,,sym∧qcvvhhqwhqqyfn|≥*2n|[#usfkvvuu¬∧wsxxyu
215 whpwauyhhw∧mfkuypccvhpvcvxsshhyjjsiusmv¬j∧qywvvcvvpvgb∧∧¬ppp
215 yyhhqwhsxmxssx¬wlppvcvxs ≥≥q|π↓qpl violate a
219 slight strengthening of Fermat's test: Eithejc|ε≥SgcNg↓≠↓*4g3
224 ←4←πmod|4←ε,|=←↔**α=↓*441 |πor there will bd somes|≥≡S4|¬JC41λ
229 |πsukh thaz |≥↑]gkK¬JfN4↓↓455|[↓kff|≥*5544}}Q4/C4*24\QUur)(≤↓↓
231 *2*266V¬K()|((44[[mbF44\*2N44}}Q46N4↓↓455 [↓kff|\≤cV3644[[mof|4
232 Q*2n|6α≡I43. |πIn fact, if a well-known number-theoretic
239 conjecbe proved, there will be some such |εq|4|¬E|4c(|πln|4|
246 εn)|g2, |πfor some constant |εc. [|π|εJ. Comp.
253 System Sci. |π|≡1|≡1 (1975), |πto appear.] If
260 number theorists succeed in proving su∃ciently
266 good explicit upper bounds for the least |εk|πth
274 power nonresidues modulo given primes, Miller's
280 approach would yield a practical algorithm for
287 testing primality in order (log|4|εn)|g5 |πsteps.
293 Alternatively it would su∃ce for practical purposes
300 to have a decent bound on |εq |πwhich works for
310 all |εn|4|¬W|410|g1|g0|g0, |πsay.|'|'|≡F|≡a|≡c|≡t|≡o|≡r|≡i|≡
314 n|≡g |≡v|≡i|≡a |≡c|≡o|≡n|≡t|≡i|≡n|≡u|≡e|≡d |≡f|≡r|≡a|≡c|≡t|≡
317 i|≡o|≡n|≡s|≡.|9|4The factorization procedures
320 we have discussed so far will often balk at numbers
330 of 30 digits or more, and another idea is needed
340 if we are to go much further. Fortunately there
349 is such an idea; in fact, there were two ideas,
359 due respectively to A. M. Legendre and M. Kraitchik,
368 which D. H. Lehmer and R. E. Powers used to devise
379 a new technique many years ago [|εBull. Amer.
387 Math. Soc. |π|≡3|≡7 (1931), 770<776]. However,
393 the method was not used at that time because
402 it wasscomparazivxwyhunfuupw∧gz fmgnfdskkckwckwwtogk)λThissn
404 egjzpvd judgment prevailed until the late 1960?,
411 whennJommnBgcllhwjo foundfthat the Lehmer<5owers
415 approach ddserved to be resurrected, since it
422 was quiteswell-suited to computer programming.
427 In fact, he and Michael A. Morrison later developed
436 it into the current champion of all methods for
445 factoring large numbers: It handles typical 25-digit
452 numbers in about 30 seconds, and 40-digit numbers
460 in about 50 minutes, on an IBM 360/91 computer
469 [see |εMazh..Comp. |π|≡2|≡9 (1975), 183<205].
474 In 1970 the method had its _rst triumphant success,
483 discovering that 2|g1|g2|g8|4α+↓|41|4α=↓|459649589127497217|
485 4|¬O|45704689200685129054721.|'!|9|441←1←11hysbjsicniddasis|
486 '{A6}|εn|β6←4α≡↓*348*5769*52677117←4←¬B|42352<\7α104401.];{J6}N
487 π'Thissrjsuqlhcv¬q∧f|\*2moh|[[q¬¬sxbefnnfifcovdred
488 by Aggorithm A in a reasonable length of time;
497 a fdwumvplivmnipzjjwpvmfsmxfUWgggcphmmnXi∧¬qgd
499 probabpy have su∃ced.|''''''''''''''''''''''''''''''''''''''
502 ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
502 ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
502 ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
502 ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
502 ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
502 ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
502 ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
502 ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
502 '''''*?*?*?*?!|9|4|1|1|1The calculations are complete;
506 the prime factorization of 2|g2|g1|g4|4α+↓|41
511 is|'{A6}|ε5|4|¬O|4857|4|¬O|4843589|4|¬O|48174912477117|4|¬O|
512 423528569104401|4|¬O|4n|β0,|;{A6}|πwhere |εn|β0
515 |πis the 29-digit prime in (15). A certain amount
524 of good fortune entered into these calculations,
531 for if we had not started with the known factorization
541 (14) it is quite probable that we would _rst
550 have cast out the small factors, reducing |εn
558 |π+o |εn|β6n|β0; |πthis 55-|πdigit number would
564 have been much more di∃cult to factor#Algorithm
571 D would be useless and Algorithm B would have
580 to work overtime because of the high precision
588 necessary.|'!|9|4|1|1←1Dozens of further numerical
593 examples can be found in an article by John Brillhart
603 and J. L.λSelfridgd, |εMath. Comp. |π|≡2|≡1 (1967),
610 87<96.|'!|:*34←1|51|1Tysbasicnidea is to search
615 for numbers |εx |πand |εy |πsuch that|'{A6}|εx|g2|4|"o|4y|g2
622 |4(|πmodulo|4|εN),!!0|4|¬W|4x,|4y|4|¬W|4N,!!x|4|=|↔6α=↓|4y,!
622 !x|4α+↓|4y|4|=|↔6α=↓←4].|J!(17)|;{A6}|πFermat's
624 mdzhodfivvgxssshhyssygong∧jccjquurjxxfmh|≥*2Fg3N4↓≠↓*44;Sv3]4(
624 *2↓N4],λ|π~kz actually thescongruence (17) is
629 enough to split |εN |πinto factors: It implies
637 that |εN |πis a divisor of |εx|g2|4α_↓|4y|g2|4α=↓|4(x|4α_↓|4
643 y)(x|4α+↓|4y), |πyet |εN |πdivides neither |εx|4α_↓|4y
649 |πnor |εx|4α+↓|4y; |πhence gcd(|εN,|4x|4α_↓|4y)λ|π_nd
653 gcd(|εN,|4)|4α+↓|4y) |πare proper factors ofs|εN
658 |πwhich can be found by Euclid's algorithm.|'
665 |π$|9*3441←1←13nfswaystonfkukgvdjcsxgqqpvmfsmxf(7*2)iushompgok
665 kfxgcv¬wqussmxf|\*2x|[)ukvhhhqwh|≥*2Xg2]44""N4_s(←π.mbkwgn|ε)↔
665 ,|[)xrcsxkwlpv¬wuassmxf|≥\¬}jU¬}7.|[↓usqwsqqplpsse↔,iphiusmx
665 xzfnuusuvvle mattej to piukjstogdzhej sbguqivmfsmxfhhiuscvmv
669 gkufckshommbbwucnsxgqqpvmfsmxf)7).NM∧qikf|≥*2XV364*2**4_U4~↓4≡K
669 fFv3/|π)xgcsxmes|≥*2k|π≠kdf|ε≠↔,|[≤qphhsx¬wlp|ε≥N¬GU¬G,
670 |π"he fraction |εx/d |πis a good approximation
677 to |¬H|v4←εkN|)←1|1;λ|π/onversewq↔,if |ε)≡-f|π/s
680 an esqekially good approximation to |¬H|v4|εkN|)|1|1,
686 |¬Gx|g2|4α_↓|4kNd|g2|¬G |πεill be small.λThis
690 observation suggests looking at the continued
696 fraction expansion of |¬H|v4|εkN|)|1|1, |π↔ucce
701 weshq¬d sses(<q)λ4#7#3↓↓3)↔thaz conopckud frjkvigns
705 yuawd goodfrationjwiaqproxumazions.|''⊗!|::44555557Vmmpckudf
707 fkjkvpvmfsfxgcqqujjjwpccicrjwpvmkwpppusshp¬¬sm¬kxy
708 plauukmh propdrties, which are proved in exercise
715 4.5.3<12. The algorithm below makes use of these
723 propejoiesstonddjcvkssxgqwivmfshomhhsscvmvgkufckS]↓{**}\εxXV3
723 644["M4(→(≤↓↓(V∧SC35PUkjsIβ15)5(*2PUkjSI⊃6X*26((44}¬MI4}¬M44}¬
723 M45p|krsIcmN)m|)|4(|πmodulo|4|εN).|J!(18)|;{A6}|πHejdswasuus
724 suu=*2xdfsszhmxfsx¬wlppvcvxss \≥PI154*2466,pPI⊃6I*2477,47[4s
726 will never be factors of the numbers generated
734 bx the algorithm (see exercise 14). If (|εx|β1,|4e|β0|β1,|4e
741 |β1|β1,|4.|4.|4.|4, e|βm|β1),|4.|4.|4.|4, (x|βr,|4e|β0|βr,|4
743 e|β1|βr,|4.|4.|4.|4, e|βm|βr) |πare solutions
747 of (18) such that the vector sum|'{A6}|ε(e|β0|β1,|4e|β1|β1,|
754 4.|4.|4.|4,|4e|βm|β1)|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4(e|β0|βr,|4e
754 |β1|βr,|4.|4.|4.|4,|4e|βm|βr)|4α=↓|4(2e|=|β0αO↓,|42e|=|β1αO↓
754 ,|4.|4.|4.|4,|42e|=|βmαO↓)!(19)|?{A6}|πis |εeven
757 |πin each component, then|'{A6}|εx|4α=↓|4(x|β1|4.|4.|4.|4x|β
761 r)|4|πmod|4|εN,!!y|4α=↓|4|≥1(|→α_↓1)|ure|β0|)|)p|ure|β1|)1|)
761 |4.|4.|4.|4p|ure|βt|)m|))|4|πmod|4|εN|J!(20)|;
762 {A6}|πyields a solution to (17), except for the
770 possibility that |εx|4|"o|4|→|¬Ny. |πCondition
774 (19) essentially says that the vectors are linearly
782 dependent modulo 2, so we must have a solut{U0}{H10L12M29}|π
folio 500 galley 10
790 W58320#Computer|9Programming!ch. 4!f. 500!g.
793 10|'{A6}|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m |≡E (|εFactoring
797 via continued fractions).|9|πGiven a positive
802 integer |εN |πand a positive integer |εk |πsuch
810 that |εkN |πis not a perfect square, this algorithm
819 attempts to discover solutions to the congruence
826 (18) for _xed |εm, |πby analyzing the convergents
834 to the continued fraction for |ε|¬H|v4kN|)|1|1.
840 |π(Another algorithm, which uses the outputs
846 to discover factors of |εN, |πis the subject
854 of exercise 12.)|'{A6}{I1.9H}|≡E|≡1|≡.|9[Initialize.]|9Set
858 |εD|4|¬L|4kN, R|4|¬L|4|"l|¬H|v4D|)|1|"L, R|¬S|4|¬L|42R,
861 U|4|¬L|4u|¬S|4|¬LR|¬S, V|4|¬L|41, V|1|¬S|4|¬L|4D|4α_↓|4R|g2,
863 P|4|¬L|4R, P|¬S|4|¬L|41, A|4|¬L|40, S|4|¬L|40.
868 |π(This algorithm follows the general procedure
874 of exercise 4.5.3<12, _nding the continued fraction
881 expansion of |ε|¬H|v4kN|)|1. |πThe variables
886 |εU, U|¬S, V, V|1|¬S, P, P|¬S, A, S |πrepresent,
895 respectively, what that exercise calls |εR|4α+↓|4*/Uβn,
901 R|4α+↓|4U|βn|βα_↓|β1, V|βn, V|βn|βα_↓|β1, p|βn
905 |πmod |εN, p|βn|βα_↓|β1 mod |εN, A|βn, |πand
912 |εn |πmod 2. We will always have |ε0|4|¬W|4V|4|¬E|4U|4|¬E|4R
919 |¬S, |πso the highest precision is needed only
927 for |εP |πand |εP|¬S.)|'{A3}|π|≡E|≡2|≡.|9[Step
932 |εU, V, S.]|9|πSet |εT|4|¬LH47, V|4←¬L|4A(U|¬S|4α_↓|4U)|4α+↓
936 |4V|1|¬}F,nV|5¬S|4|¬L|4T, A|4|¬L|4|"l(R|4α+↓|4U)/V|"L,
938 U|¬S|4|¬L|4U, U|4|¬L|4R|¬S|4α_↓|4(U|4|πmod|4|εV),
940 S|4|¬L|41|4α_↓|4S.|'{A3}|π|≡E|≡3|≡.|9[Factor
942 |εV.]|9|π(Now we have |εP|g2|4α_↓|4kNQ|g2|4α=↓|4(|→α_↓1)|gSV
945 , |πfor some |εQ |πrelatively prime to |εP, |πby
954 exercise 4.5.3(c).|≥2 Set |ε(e|β0,|4e|β1,|4.|4.|4.|4,
958 e|βm)|4|¬L|4(SF,|||444444444*?*?*? exercise 4.5.3(c).|≥2
961 Set |ε(e|β0,|4e|β1,|4.|4.|4.|4, e|βm)|4|¬L|4(S,|40,|4.|4.|4.
963 |4,|40), T|4|¬L|4V. |πNow do the following, for
970 1|4|¬E|4|εj|4|¬E|4m: |πIf |εT |πmod |εp|βj|4α=↓|40,
975 |πset |εT|4|¬L|4T/p|βj |πand |εe|βj|4|¬L|4e|βj|4α+↓|41,
979 |πand repeat this process until |εT |πmod |εp|βj|4|=|↔6α=↓|4
986 0.|'{A3}|π|≡E|≡4|≡.|9[Solution?]|9If |εT|4α=↓|41,
989 |πoutput the values |ε(P,|4e|β0,|4e|β1,|4.|4.|4.|4,|4e|βm),
993 |πwhich comprise a solution to (22). (If enough
1001 solutions have been generated, we may terminate
1008 the algorithm now.)|'{A3}|≡E|≡5|≡.|9[Step |εP,
1013 P|¬S.]|9|πIf |εV|4|=|↔6α=↓|41 |πor |εU|4|=|↔6α=↓|4R|¬S,
1017 |πset |εT|4|¬L|4P, P|4|¬L|4(AP|4α+↓|4P|¬S) |πmod
1021 |εN, P|¬S|4|¬L|4T. |πOtherwise the continued
1026 fraction process has started to repeat its cycle,
1034 except perhaps for |εS, |πso the algorithm terminates.
1042 (The cycle will usually be so long that this
1051 doesn't happen, unless |εkN |πis nearly a perfect
1059 square. For the length of cycle, cf. D. R. Hickerson,
1069 |εPaci⊂c J. Math. |π|≡4|≡6 (1973), 429<432; D.
1076 Sharks, |εProc. Boulder Number Theory Conference
1082 (|πU. of Colorado: 1972), 217<224.)|'|'{IC}!|9|4|1|1|1Best
1089 results will occur, of course, when |εk |πand
1097 |εm |πare chosen appropriately. A large value
1104 of |εk |πmakes the |εV |πnumbers larger (hence
1112 less likely to factor), while a good value of
1121 |εk |πmakes them divisible by more small primes
1129 (hence more likely to factor), so we want to
1138 balance these tendencies. Consider, for example,
1144 the divisibility of |εV |πby powers of 5. We
1153 have |εP|g2|4α_↓|4kNQ|g2|4α=↓|4(|→α_↓1)|gSV |πin
1156 step E3, so if 5 divides |εV |πwe have |εP|g2|4|"o|4kNQ|g2
1166 (|πmodulo 5). Here |εQ |πcannot be a multiple
1174 of 5, since it is relatively prime to |εP, |πso
1184 we may write |ε(P/Q)|g2|4|"o|4kN. |πIf we assume
1191 that |εP |πand |εQ |πare random relatively prime
1199 integers, so that the 24 possibilities of (|εP
1207 |πmod 5, |εQ |πmod 5)|4|=|↔6α=↓|4(0,|40) are
1213 equally likely, the probability that |ε5|¬DV
1219 |πis therefore |f4|d324|), |f8|d324|), 0, 0,
1225 or |f8|d324|) according as |εkN |πmod 5 is 0,
1234 1, 2, 3, or 4.mSimilarly the probability that
1242 |ε25|¬DV |πis 0, |f40|d3600|), 0, 0, |f40|d3600|)
1249 respectively, unless |εkN |πis a multiple of
1256 25. In general, given an odd prime |εp |πwith
1265 (|εkN)|ur(pα_↓1)/2|)|) |πmod |εpα=↓1, |πwe _nd
1270 that |εV |πis a multiple of |εp|ge |πwith probability
1279 |ε2/p|ge|gα_↓|g1(|1p|4α+↓|41); |πand the average
1283 number of times |εp |πdivides |εV |πcomes to
1291 |ε2p/(|1p|g2|4α_↓|41). |πThis analysis, suggested
1295 by R. Schroeppel, suggests that the best choice
1303 of |εk |πis that which maximizes|'{A2}|ε|↔k|uc|)p|1|1|1|πpri
1309 me|)|4|εf(|1p,|4kN)|4|πlog|4|εp|4α_↓|4|f1|d32|)|4|πlog|4|εk,
1309 |J!(18)|;{A6}|πwhere |εf |πis the function de_ned
1316 in exercise 13, for this is essentially the expected
1325 value of the logarithm of |ε|¬H|v4N|)/T |πwhen
1332 we reach step E4.|'!|9|4|1|1|1Before we study
1339 the choice ov |εm, |πlet us consider an important
1348 re_nement of Algorithm E: Comparing step E3 with
1356 Algorithm A, we see that the factoring of |εV
1365 |πcan stop whenever we _nd |εT |πmod |εp|βj|4|=|↔6α=↓|40
1373 |πand |ε|"lT/p|βj|"L|4|¬E|4p|βj, |[(unce |εT
1377 |πwill then be 1 or prime. If |εT |πis a prime
1388 greater than |εp|βm (|πit will be at most |εp|βm|g2|4α+↓|4p|
1396 βm|4α_↓|41) |πwe can still output (|εP,|4e|β0,|4.|4.|4.|4,
1402 e|βm, T), |πsince a complete factorization has
1409 been obtained. The second phase of the algorithm
1417 will use only those outputs whose prime |εT'|πs
1425 |πhave occurred at least twice. This modi_cation
1432 gives the e=ect of a much longer list of primes,
1442 without increasing the factorization time.|'!|9|4|1|1←1]ow
1448 lez'? makesa heurcstic analysis of the running
1455 time of Algorithm E, following unpublished ideas
1462 of R. Schroeppel: We assume that |εk|4α=↓|41,
1469 |πto get an upper bo¬kf) The number of outputs
1478 needed to produce a factorization of |εN, |πusing
1486 the modi_cation in the preceding paragraph, will
1493 be roughly proportional to |ε|≤p(p|βm|g2)|4|¬V|4(m/|πlog|4|ε
1497 m)|g2, |πlet's say |εm|g2. |πEach execution of
1504 step E3 will take about order |εm |πunits of
1513 time; and if we assume that |εV |πis randomly
1522 distributed between 0 and |ε2|¬H|v4N|) |πour
1528 chance of successful output per iteration will
1535 be approximately |εF|≥1(|πlog|4|εp|βm|g2)/(|πlog|42|ε|¬H|v4N
1537 |)|1)|≥2, |πwhere |εF |πis Dickman's function
1543 of Fig. 11. Therefore the total running time
1551 is roughly proportional to|'{A6}|ε|εm|g3/F(1/|≤a),!!|≤a|4α=↓
1555 |4(|πlog|4|ε2|¬H|v4N|)|1)/(|πlog|4|εp|βm|g2).|J!(19)|;
1556 {A6}|πIt is possible to show that |εF(1/|≤a)|4α=↓|4|πexp(|ε|
1562 →α_↓|≤a|4|πln|4|ε|≤a|4α+↓|4O(|≤a|4|πlog|4log|4|ε|≤a)|≥2
1563 |πaus |ε*?*?It is possible to show that |εF(1/|≤a)|4α=↓|4|πexp
1570 (|ε|→α_↓|≤a|4|πln|4|ε|≤a|4α+↓|4O(|≤a|4|πlog|4log|4|ε|≤a)|≥2
1571 |πas |ε|≤a|4|¬M|4|¬X; |πin fact, N. G. de Bruijn
1579 [|εJ. Indian Math. Soc. |π|≡1|≡5 (1951), 25<32]
1586 has obtained a much sharper estimate. If we now
1595 choose ln|4|εm|4α=↓|4|¬H|v4(|πln|4|εN)(|πln|4ln|4|εN)/24|)
1597 |πwe _nd that (19) becomes exp(|¬H|v4|f3|d32|)(ln|4|εN)(|πln
1602 |4ln|4|εN)|)|4α+↓|4O|≥1(|πlog|4|εN)|g1|g/|g2(|πlog|4log|4|εN
1602 )|gα_↓|g1|g/|g2(|πlog|4log|4log|4|εN)|≥2. |πNote
1604 that the running time is order |εN|g|≤o|g(|gN|g),
1611 |πwhere |ε|≤o(N)|4|¬V|4|¬H|v4|f3|d32|)(|πln|4ln|4|εN)/(|πln|
1612 4|εN)|) |πgoes to 0 as |εN|4|¬M|4|¬X*3 |πThese
1619 asymptotic formulas are too crude to be applied
1627 for |εN |πin a practical range, however; several
1635 years' experience by Morrison and Brillhart suggests
1642 that |εm |πshould be approximately 25(log|β1|β0|4|εN|4α_↓|41
1647 4) |πfor 10|g2|g5|4|¬W|4|εN|4|¬W|410|g5|g0.|'
1650 !|9|4|1|1|1|πSince step E3 is by far the most
1658 time-consuming part of the algorithm, Morrison,
1664 Brillhart, and Schweppel have suggested several
1670 ways to abort this step when success becomes
1678 improbable: (a) Whenever |εT |πchanges to a single-precision
1685 value, continue only if |"l|εT/p|βj|"L|4|¬Q|4p|βj
1691 |πand |ε3|gT|gα_↓|g1|4|πmod|4|εT|4|=|↔6α=↓|41.
1693 |π(b) Give up if |εT |πis still |ε|¬Qp|βm|g2
1701 |πafter casting out factors |¬W|f1|d310|)|εp|βm.
1706 |π(c) Cast out factors only up to |εp|β5, |πsay,
1715 for batches of 100 or so consecutive |εV'|πs;
1723 continue the fakvorization later, but only on
1730 the |εV |πfrom each batch which has produced
1738 the smallest residual |εT.|'|'|π|≡O|≡t|≡h|≡e|≡r
1744 |≡a|≡p|≡p|≡r|≡o|≡a|≡c|≡h|≡e|≡s|≡.|9|4A completely
1746 di=erent method of factorization, based on composition
1753 of binary quadratic forms, has been introduced
1760 by Daniel Shanks |ε[Proc. Symp. Pure Math. |π|≡2|≡0
1768 (1971), 415<440]. Like Algorithm B it will factor
1776 |εN |πin |εO(N|ur(1/4)α+↓|≤o|)|)) |πsteps except
1781 under wildly improbable circumstances.|'!|9|4|1|1|1Still
1786 another important technique has been suggested
1792 by John M. Pollard [|εProc. Cambridge Phil. Soc.
1800 |π|≡7|≡6 (1974), 521<528]. He obtains rigorous
1806 worst-case bounds of |εO(N|ur(1/4)α+↓|≤o|)|))
1810 |πfor factorization and |εO(n|ur(1/8)α+↓|≤o|)|))
1814 |πfor primality testing, but with impracticably
1820 high coe∃cients of proportionawppy; and he also
1827 gives a practical algorithm for discovering prime
1834 factors |εp |πof |εN |πwhen |εp|4α_↓|41 |πhas
1841 no large prime factors. The latter algorith{U0}{H10L12M29}|π
folio 505 galley 11
1847 W58320#Computer Programming!ch. 4!f. 505!g. 11|'
1852 {A6}!|9|4|1|1|1We can illustrate the application
1857 of Algorithm E to relatively small numbers by
1865 considering the case |εN|4α=↓|4197209, |εk|4α=↓|41,
1870 m|4α=↓|43, p|β1|4α=↓|42, p|β2|4α=↓|43, p|β3|4α=↓|45.
1874 |πThe computation proceeds as follows:|'|'{H7L8}|∂!!!!!!|∂>
1881 !!|∂!!!|∂!!!|∂!!!!!|∂!!!|∂!!!|∂!!!!!!!!!|∂|E|;
1882 |>|;|εU|;V|;A|;P|;S|;T|;|πOutput|;>{A2}|>After|4E1:|'
1894 888|;!|1|11|;|9|10|;!|9|1|1|1444|;0|;#|;>|>After|4E4:|'
1903 876|;|9|173|;12|;!|9|1|1|1444|;1|;|9|173|;>|>
1911 After|4E4:|'882|;145|;|9|16N;!|1|15329|;0|;|9|12α|;
1917 >|>After|4E4:|'857|;|9|137|;23|;|9|132418|;1|;
1925 |9|137|;>|>After|4E4:|'751|;720|;|9|11|;159316|;
1933 0|;!|1|11|;159316|g2|4|"o|42|g4|4|¬O|43|g2|4|¬O|45|g1|'
1936 >|>After|4E4:|'852|;143|;|9|15|;191734|;1|;143|;
1945 >|>After|4E4:|'681|;215|;|9|13|;\331954;0|;*3:←143|;
1953 >|>After|4E4:|'863|;656|;|9|11|;193139|;1|;|9|141|;
1962 >|>After|4E4:|'883|;←9|133|;26←;127873←;0|;|9|111|;
1969 >⊗|>Aftej|4E4:*3'823←;*536|;|9←16];165232|;1|;|9|117|;
1975 %⊗|>AfxzjC4S*/:Y'<77];*/05←;←9|12|;133218|;0|;!|1|11←;133218|g
1979 2|4|"o|42|g0|4|¬O|43|g4|4|¬O|45|g1|'>|>Afzer|4E4:|'
1983 875←;|9|126←;36|;|9|137250|;1|;8|1|111|;|9*?|>
1988 After|4E4:|'875|;|9|124|;36|;|9|137250|;1|;!|1|11|;
1995 |9|137250|g2|4|"o|4|→α_↓2|g3|4|¬O|43|g1|4|¬O|45|g0|'
1996 >|>After|4E4:|'490|;477|;|9|11|;|9|193755|;0|;
2004 |9|153|;>{A12}{H10L12}!|9|4|1|1|1Continuing the
2008 computation gives 25 outputs in the _rst 100
2016 iterations; in other words, the algorithm is
2023 _nding solutions quite rapidly. Some of the solutions
2031 are trivial; for example, if the above computation
2039 were continued 13 more times, we would obtain
2047 the output 197197|g2|4|"o|42|g4|4|¬O|43|g2|4|¬O|45|g0,
2050 which is of no interest since 197197|4|"o|4|→α_↓12.
2057 But the _rst two solutions above are already
2065 enough to complete the factorization: We have
2072 found that|'{A6}(159316|4|¬O|4133218)|g2|4|"o|4(2|g2|4|¬O|43
2074 |g3|4|¬O|45|g1)|g2!!(modulo|4197209);|;{A6}hence
2076 (17) holds with |εx|4α=↓|4159316|4|¬O|4133218
2080 mod 197209|4α=↓|4126308, |εy|4α=↓|4540. |πBy
2084 Euclid's algorithm, gcd(126308|4α_↓|4540, 197209)|4α=↓|4199;
2087 hence we obtain the pretty factorization|'{A6}197209|4α=↓|4
2094 199|4|¬O|4991.|;|'|≡T|≡h|≡e |≡l|≡a|≡r|≡g|≡e|≡s|≡t
2098 |≡k|≡n|≡o|≡w|≡n |≡p|≡r|≡i|≡m|≡e|≡s|≡.|9|1|1|1|1We
2100 have discussed several computational methods
2105 elsewhere in this boo¬ which require the use
2113 of large prime numbers, and the techniques described
2121 in this section can be used to discover primes
2130 of, say, 25 digits or less, with relative ease.
2139 Table 1 shows the ten largest primes which are
2148 less than the word size of typical computers;
2156 some other useful primes appear in the answer
2164 to exercise 4.6.4<14.|'!|9|4|1|1|1Actually much
2169 larger primes of special forms are known, and
2177 it is occasionally important to _nd primes which
2185 are as large as possible. Let us therefore conclude
2194 this section by investigating the interesting
2200 manner in which the largest explicitly known
2207 primes have been discovered. Such primes ajjsmf
2214 the form |ε2|gn|4α_↓|41, |πfor various special
2220 values of |εn, |πand so they are especially suited
2229 to certain applications of binary computers.|'
2235 {A12}{H10L12}|∨T|∨a|∨bS∨l|∨e|4|4|∨3|;{H7L9}USEFKL|9PRIME|9NU
2236 MBERS|;|J#>{H7L9}|∂!!!!|9|4|∂!!!!|9←∂$!!!|9|∂!!!!|9*3∂$!!!|9*3
2238 ∂!!!!|9←∂$!!!|9|∂!!!!|9*3∂!!!!|9|∂!!!!|9|∂!!!!|9|∂|SS|;
2239 |>|εN|;a|β1|;a|β2|;a|β3|;a|β4|;a|β5|;a|β6|;a|β7|;
2248 a|β8|;a|β9|;a|β1←β0|;>|>!|92|g1|g5|'19!|9|?49!|9|?
2256 51!|9|?55!|9|?61!|9|?75!|9|?81!|9|?115$|9|?121!|9|?
2263 135$|9|?>|>!|92←g1←g6]'35$|9*3?*57!|9*3?α9|9|?57`|9←?82|9|?
2268 898|9*3?998|9←?*5133|9|?\177|9H?*523∨|9|?>⊗-|>|π!|92←g1|g7|'
2273 1!|9|?9!|9|?13$|9|?31!|9|?498|9|?61$|9|?63`|9|?
2280 85!|9|*3?91*?*?*?|>|π!|92|g1|g7|'1!|9|?9!|9|?13!|9|?
2285 31!|9|?49!|9|?61!|9|?63!|9|?85!|9|?91!|9|?99!|9|?
2292 >|>!|92|g1|g8|'5!|9|?11!|9|?17!|9|?23!|9|?33!|9|?
2300 35!|9|?41!|9|?65!|9|?75!|9|?93!|9|?>|>!|92|g1|g9|'
2308 1!|9|?19!|9|?27!|9|?31!|9|?45!|9|?57!|9|?67!|9|?
2315 69!|9|?85!|9|?87!|9|?>|>!|92|g2|g0|'3!|9|?5!|9|?
2323 17!|9|?27!|9|?59!|9|?69!|9|?129!|9|?143!|9|?153!|9|?
2330 185!|9|?>|>!|92|g2|g1|'9!|9|?19!|9|?21!|9|?55!|9|?
2338 61!|9|?69!|9|?105!|9|?111!|9|?121!|9|?129!|9|?
2344 >|>!|92|g2|g2|'3!|9|?17!|9|?27!|9|?33!|9|?57!|9|?
2352 87!|9|?105!|9|?113!|9|?117!|9|?123!|9|?>|>!|92|g2|g3|'
2360 15!|9|?21!|9|?27!|9|?37!|9|?61!|9|?69!|9|?135!|9|?
2367 147!|9|?157!|9|?159!|9|?>|>!|92|g2|g4|'3!|9|?
2374 17!|9|?33!|9|?63!|9|?75!|9|?77!|9|?89!|9|?95!|9|?
2381 117!|9|?167!|9|?>|>!|92|g2|g5|'39!|9|?49!|9|?
2388 61!|9|?85!|9|?91!|9|?115!|9|?141!|9|?159!|9|?
2394 165!|9|?183!|9|?>|>!|92|g2|g6|'5!|9|?27!|9|?45!|9|?
2402 87!|9|?101!|9|?107!|9|?111!|9|?117!|9|?125!|9|?
2408 135!|9|?>|>!|92|g2|g7|'39!|9|?79!|9|?111!|9|?
2415 115!|9|?135!|9|?187!|9|?199!|9|?219!|9|?231!|9|?
2421 235!|9|?>|>!|92|g2|g8|'57!|9|?89!|9|?95!|9|?119!|9|?
2429 125!|9|?143!|9|?165!|9|?183!|9|?213!|9|?273!|9|?
2435 >|>!|92|g2|g9|'3!|9|?33!|9|?43!|9|?63!|9|?73!|9|?
2443 75!|9|?93!|9|?99!|9|?121!|9|?133!|9|?>|>!|92|g3|g0|'
2451 35!|9|?41!|9|?83!|9|?101!|9|?105!|9|?107!|9|?
2457 135!|9|?153!|9|?161!|9|?173!|9|?>|>!|92|g3|g1|'
2464 !|91|?19!|9|?61!|9|?69!|9|?85!|9|?99!|9|?105!|9|?
2471 151!|9|?159!|9|?171!|9|?>|>!|92|g3|g2|'5!|9|?
2478 17!|9|?65!|9|?99!|9|?107!|9|?135!|9|?153!|9|?
2484 185!|9|?209!|9|?267!|9|?>|>!|92|g3|g3|'9!|9|?
2491 25!|9|?49!|9|?79!|9|?105!|9|?285!|9|?301!|9|?
2497 303!|9|?321!|9|?355!|9|?>|>!|92|g3|g4|'41!|9|?
2504 77!|9|?113!|9|?131!|9|?143!|9|?165!|9|?185!|9|?
2510 207!|9|?227!|9|?281!|9|?>|>!|92|g3|g5|'31!|9|?
2517 49!|9|?63!|9|?6α!|9|?79!|9|?121!|9|?141!|9|?247!|9|?
2524 309!|9|?325!|9|?>|>!|92|g3|g6|'5!|9|?17!|9|?23!|9|?
2532 65!|9|?117!|9|?137!|9|?159!|9|?173!|9|?189!|9|?
2538 233!|9|?>|>!|92|g3|g7|'25!|9|?31!|9|?45!|9|?69!|9|?
2546 123!|9|?141!|9|?199!|9|?201!|9|?351!|9|?375!|9|?
2552 >|>!|92|g3|g8|'45!|9|?87!|9|?107!|9|?131!|9|?
2559 153!|9|?*585!|9|?191!|9|?227!|9|?231!|9|?257!|9|?
2565 >|>!|92|g3|g9|'7!|9|?19!|9|?67!|9|?91!|9|?135!|9|?
2573 165!|9|?219!|9|?231!|9|?241!|9|?301!|9|?>|>!|92|g4|g0|'
2581 87!|9|?167!|9|?195!|9|?203!|9|?213!|9|?285!|9|?
2587 293!|9|?299!|9|?389!|9|?437!|9|?>|>!|92|g4|g1|'
2594 21!|9|?31!|9|?55!|9|?63$|9|?73!|9|?75!|9|?91!|9|?
2601 111!|9|?133!|9|?139!|9|?>|>!|92|g4|g2|'11!|9|?
2608 17!|9|?33!|9|?53!|9|?65!|9|?143!|9|?161!|9|?165!|9|?
2615 215!|9|?227!|9|?>|>!|92|g4|g3|'57!|9|?67!|9|?
2622 117!|9|?175!|9|?255!|9|?267!|9|?291!|9|?309!|9|?
2628 319!|9|?369!|9|?>|>!|92|g4|g4|'17!|9|?117!|9|?
2635 119!|9|?129!|9|?143!|9|?*549!|9|?287!|9|?327!|9|?
2641 359!|9|?377!|9|?>|>!|92|g4|g5|'55!|9|?69!|9|?
2648 81!|9|?93!|9|?121!|9|?133!|9|?139!|9|?159!|9|?
2654 193!|9|?229!|9|?>|>!|92|g4|g6←'23!|9*3?57!|9:?**7∨|9|?
2659 77∨|9|?167$|9|?197!|9|?↑37!|9←?↑87!|9*3?↓π5!|9*3?31!|9S?*/⊗|>
2663 !|92|g4|g7|'115!|9|?127!|9|?147!|9|?279!|9|?297!|9|?
2669 339!|9|?435!|9|?\41!|9|?**39!|9|?669!|9|?>|>!|92|g4|g8|'
2677 59!|9|?65!|9|?89!|9|?93!|9|?147$|9|?165!|9|?189!|9|?
2684 233!|9|?243!|9|?257!|9|?>|>!|92|g5|g9|'55!|9|?
2691 99!|9|?225!|9|?427!|9|?517!|9|?607!|9|?649!|9|?
2697 687$|9|?8**3!|9|?871$|9←?%|>!|92|g6|g0|'93!|9|?
2702 107!|9←?*573∨|9←?17α8|9|?257$|9|?27α!|9|?36α8|9|?
2706 ↓\$|9|?↓↓98|9*3?*/53`|9:?*/∂|>$|92|g6]g3←'25!|9←?165$|9*3?↑798|9
2708 ←?3π1!|9|?377T|9|?3<7!|9|?↓91!|9←?409!|9|?457!|9|?
2713 471!|9|?>|>!|92←g6|g4|'79!|9|?83!|9|?95!|9|?179!|9|?
2721 189!|9|?257!|9|?279!|9|?323!|9|?353!|9|?↓63!|9|?
2727 %⊗|>!|910|g6],37`|9←?↑3$|9|?↓8|9*3?*/51|9*3?*/77|::?6(8|::?*3↓2|:
2729 :*3:↓3|::?\177|::?\377|::?*/∂|4>|:*50→g77,α9|9*3?**77|9*3?**↓9|9*3?\
2730 77|::?**73|::?**9|::?71|::?:↓3|::?:99|::?\111|::?=∂|4>
2731 |:*51→V↓*3]311|::*3**↓9|::?*/51|::?≥\9|::?**9|::?≥573|Y:?≥771|::?≥
2731 773|Y:S≥79|H:|≡333||9|?>|>!|910|g9*3'63`|9|?73!|9|?
2736 1072|9*3?117`|9←?↑π3`|9:*3**3↓8|::*3**673|::*3≡6\9|::*3≡671|Y:*3≡677
2736 ||:|=> >!|911→g1|g0←]33!|9|?\7$|9*3?71|::*3\1*59|::*3\5\9|::*3≥77
2740 7|::S=1↑3|S:S≡233!|9|↔219!|9|?231!|9|?>|>!|910|g1←g1←'23$|::
2744 *3\73|::*3\77|::*3;↓3|::*3\3↓9||:|=549||:|?767!|9|?
2746 171!|9|?179!|9|?233!|9|?%⊗|>!|910←V35v26,311|::*3↓9|::*3*/51|::
2750 *3≡73|Y:*3≥111||:|?323!|9|?137!|9|?143!|9|?155333!!!!!!!!!!!!!
2754 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
2754 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*?*?*?*?{U0}{H10L12M29}|πW5832
folio 508 galley 12
2754 0#Computer Programming!ch. 4!f. 508!g. 12|'{A6}|π!|9|4|1|1|1
2759 A number of the form |ε2|gn|4α_↓|41 |πcannot
2766 be prime unless |εn |πis prime, since |ε2|gu|gv|4α_↓|41
2774 |πis divisible by |ε2|gu|4α_↓|41. |πIn 1644,
2780 Marin Mersenne astonished his contemporaries
2785 by stating, in essence, that the numbers |ε2|gp|4α_↓|41
2793 |πare prime for |εp|4α=↓|42, 3, 5, 7, 13, 17,
2802 19, 31, 67, 127, 257, |πand for no other |εp
2812 |πless than 257. (This statemefo aqpeajjdficncvmnfkvpvmnquph
2817 huufkukkusuvmnmxfpujfdkg nk¬bdjksicnthesprdfjkestonhis
2819 |ε6ogitaza Physico-Mathematica. |πCuriously,λhe
2822 also made thesfbglowung rdxajk(?]`πontewlpiffauvvvjfnnk¬xdr
2826 mxf15 orcdigitssis prcvfsornnoo,,awlphivxsq∧¬q∧fnmohsu≥*2ksfx
2828 gchhyshzsy.,qqwze¬dr usesis mjjdsof wyaz is awready
2834 known.'')λMersennd↔,wyo hajfcorrjsqvndddffkjqqufmlqyquthhFfj
2835 vjw,,Ddskjrtes↔ and othejfsabout similar topics
2840 innpreviokusyeajk↔,vj¬jsnmnpvgoffoxfhpusaussjgpvmf↔,ukfffxgc
2840 mvdj 230λyeajksnmbbbxskkdwqqqezhyjcheswwuscorrjkv
2842 orcnmo.,SUqwjcsym∧wdfhhuwh66v36V354≠↓*4455iusprcmdsin
2843 1772,,afbejchaving tried uffukcjssfkqlqstonpvgv¬shhpusicnpvj
2845 ¬iouusyyarf).U{b¬qh5*575|*/≥*5(.PQkkusdiukvvered
2846 hhwt 2|g35v3|g7|4α_↓|41 is prime, but 2|g6|g7|4α_↓|41
2852 is not; hhyjjfxgjsMerfsfnd was not completely
2858 accurate. In 1883, I. M. Pervushin proved that
2866 2|g6|g1|4α_↓|41 is prime [cf. |εIstoriko-Mat.
2871 Issledovaniya |π|≡6 (1953), 559], and this touched
2878 o= speculation that Mersenne had only made a
2886 copying error, writing 67 for 61. Eventually
2893 other errors in Mersenne's statement were discovered;
2900 R. E. Powers [|εAMM |π|≡1|≡8 (1911), 195] found
2908 that 2|g8|g9|4α_↓|41 is prcmb,nas had been conjectured
2915 by some earlier writers, and three years later
2923 he found that 2|g1|g0|g7|4α_↓|41 also is prime.
2930 M. Kraitchik showed in 1922 that 2|g2|g5|g7|4↓↓|41
2937 is |εnot |πprime.|'!|9|4|1|1|1At any rate, numbers
2944 of the form |ε2|gp|4α_↓|41 aje now kfown ass|ε(ejsefnfsnkxbe
2951 jf↔,|π_fd it is knowfn[Bryant Tuckerman,|εProc.
2956 Nat. Acad. Sci. |π|≡6|≡8 (1971), 2319<2320] that
2963 the _rst 24 Mersenne primes are obtained for
2971 |εp |πequal to|'{A6}2, 3, 5, 7, 13, 17, 19, 31,
2982 61, 89, 107, 127, 521, 607, 1279,|;2203, 2281,
2991 3217, 4253, 4423, 9689, 9941, 11213, 19937.|J!(20)|;
2998 {A6}|π(Note that 8191|4α=↓|42|g1|g3|4α_↓|41 does
3002 not occur in hhpisppst; Mersenne had stated that
3010 2|g8|g1|g9|g1|4α_↓|41 is prime, and others had
3016 conjectured that any Mersenne prime could perhaps
3023 be used in the exponent.)|'!|9|4|1|1|1Since 2|g1|g9|g9|g3|g7
3029 |4α_↓|41 is a 6002-digit number, it is clear
3037 that some special techniques have been used to
3045 prove that it is prime. An e∃cient method for
3054 testing whether or not |ε2|gp|4α_↓|41 |πis prime
3061 was _rst given by |=⊂E. Lucas |ε[Amer. J. Math.
3070 |π|≡1 (1878), 184<239, 289<321, especially p.
3076 316] and improved bx D. H. Lehmer [|εAnnals of
3085 Math. |π|≡3|≡1 (1930), |π419<448, especially
3090 p. 443]. The Lucas-Lehmer test, which is a special
3099 case of the method now used for testing the primality
3109 of |εn |πwhen the factors of |εn|4α+↓|41 |πare
3117 known, is the following:|'|'|≡T|≡h|≡e|≡o|≡r|≡e|≡m
3123 |≡L|≡.|9|4|εLet q be an odd prime, and de⊂ne
3131 the sequence |↔bL|βn|↔v by the rule|'{A6}|εL|β0|4α=↓|44,!!L|
3137 βn|βα+↓|β1|4α=↓|4(L|=|βn|g2|4α_↓|42)|4|πmod|4|ε(2|gq|4α_↓|41
3137 ).|J!(21)|;{A6}|π|εThen 2|gq|4α_↓|41 is prime
3142 if and only if L|βq|βα_↓|β2|4α=↓|40.|'|'|π!|9|4|1|1|1For
3149 example, 2|g3|4α_↓|41 is prime since |εL|β1|4α=↓|4(4|g2|4α_↓
3154 |42) mod 7|4α=↓|40. |πThis test is pqjgicularly
3161 well adapted to binary calculation, using multiple-precision
3167 arithmetic whenn|εq |πis large, since calculation
3174 mod(|ε2|gq|4α_↓|41) |πis so convenient; cf. Section
3180 4.3.2.|'|'|εProof.|9|4|πWe will prove Theorem
3186 L using only very simple principles of number
3194 theory, by investigating several features of
3200 recurring sequences which are of independent
3206 interest. Consider the sequences |↔b|εU|βn|↔v,
3211 |↔bV|βn|↔v |πde_ned by|'{A6}|ε|∂U|β0|4α=↓|40,!!U|β1|4α=↓|41,
3214 !!U|βn|βα+↓|β1|4α≡↓|44U|βn|4α_↓|4U|βn|βα_↓|β1;|;
3215 {A4}|LV|β0|4α=↓|42,!!V|β1|4α=↓|44,$!V|βn|βα+↓|β1|4α=↓|447|βn
3215 |4α_↓|4V|βn|βα_↓|β1.|J!(22)2{J6}|πThe following
3217 equations are readily proved by induction:|'{A6}|εV|βn|4|∂α=
3223 ↓|4U|βn|βα+↓|β1|4α_↓|4U|βn|βα_↓|β1;!!!!!!|;{A4}| U|βn|4|Lα=↓
3224 |4|≥1(2|4α+↓|4|¬H|v23|)|1)|gn|4α_↓|4(2|4α_↓|4|¬H|v23|)|1)|gn
3224 |≥2/|¬H|v212|)|1;|J!(24)>{A2}| V|βn|4|Lα=↓|4(2|4α+↓|4|¬H|v23
3225 |)|1)|gn|4α+↓|4(2|4α_↓|4|¬H|v23|)|1)|gn|1;|J!(25)>
3226 {A4}| U|βm|βα+↓|βn|4|Lα=↓**4*/SβmU|βnNβα+↓|β1←4α_↓|4U|βm|βα_↓|
3226 β1U|βn.|J!(26)>{A6}|π!|9|4|1|1|11et us now prove
3231 an auxiliary result, when |εp |πis prime and
3239 |ε3|4|¬E|41:|'{A6}|πif!!|εU|βn|4|"o|40 (|πmodulo
3242 |εp|ge)!!|πthen!!|εU|βn|βp|4|"o|40 (|πmodulo
3244 |εp|ge|gα+↓|g1).|J!(27)];{A6}|πThis followssfrom
3246 thesmore general considerations of exercise 3.2.2<11,
3252 but a simple proof fxg this case can be given.
3262 Assume that |εU|βn|4α=↓|4bp|ge, U|βnNβα+↓|β1|4α=↓|4a.λ|πBy
3266 (26) and (22), |εU|β2|βn|4α=↓|4bp|ge(2a|4α_↓|44bq|ge)|4|""|4
3269 (2a)U|βnn(|πmodklo |εp|ge|gα+↓|g1), |πwhile |εU|β2|βn|βα+↓|β
3272 1|4α=↓|4U|ur2|)nα+↓1|)|4α_↓|4U|1|=|βn|g2|4|"o|4a|g2.
3273 |πSimilarly, |εU|β3|βn|4α=↓|4U|β2|βn|βα+↓|β1U|βn|4α_↓|4U|β2|
3274 βnU|βn|βα_↓|β1←4←""|4(3j|g2)K|βnn|πandf|ε*/Sβ37icNβα~↓*4i1←4α≡
3274 N4USβ26βcNβα"↓|β1*/|βnNβα~↓]β1←4α≠↓**4*/Uβ2]βnKUicN4←""N4=Uv3.,
3274 |[7cnv∧ffjjw/],↓{**Fπ"|εU|βk|βnN4←""|4kaUNgk|gα*?|εU|βk|βn|4|"
3274 o|4(ka|gk|gα_↓|g1)U|βn!!|πand!!|εU|βk|βn|βα+↓|β1|4|"o|4a|gk!
3274 !(|πmodulo |εp|ge|gα+↓|g1),|;{A6}|πso (27) follows
3279 if we take |εk|4α=↓|4p.|'|π!|9|4|1|1|1From formulas
3285 (24) and (25) we can obtain other expressions
3293 for |εU|βn |πand |εV|βn, |πexpanding (2|4|¬N|4|¬H|v43|)|1)|ε
3298 |gn |πby the binomial theorem:|'{A6}|ε|εU|βn|4α=↓|4|↔k|uc|)k
3303 |)|1|1|↔a|(n|d52k|4α+↓|41|)|↔s2|gn|gα_↓|g2|gk|gα_↓|g13|gk,!!
3303 V|βn|4α=↓|4|↔k|uc|)k|)|1|1|↔a|(n|d52k|)|↔s2|gn|gα_↓|g2|gk|gα
3303 +↓|g13|gk.|J!(28)|;{A6}|πNow if we set |εn|4α=↓|4p,
3309 |πwhere |εp |πis an odd prime, and if we use
3319 the fact that |ε(|fp|d3k|)) |πis a multiple of
3327 |εp |πexcept when |εk|4α=↓|40 |πor |εk|4α=↓|4p,
3333 |πwe _nd that|'{A6}|εU|βp|4|"o|43|g(|gp|gα_↓|g1|g)|g/|g2,!!V
3336 |βp|4|"o|44!(|πmodulo|4|εp).|J!(29)|;{A6}|π|πIf
3338 |εp|4|=|↔6α=↓|43, |πFermat's theorem tells us
3343 that |ε3←gp|gα_↓|g1|4|"o|41; |πmence (3|g(|gp|gα_↓|g1←g)|g/|
3346 g2N4α_↓|41)|4|¬O|4(3|ε|g(*3gp|gα_↓*4g1|g)|g/]g2N4α+↓|41)←4|""|
3346 40,n|πandn|ε↓←g(*4gp|gα_↓|g1|g)|g/|g2|4|"o|4|→|¬N1.
3347 |πWhen |εU|βp|4|"o|4|→α_↓1, |πwe have |εU|βp|βα+↓|β1|4α=↓|44
3351 U|βp|4α_↓|4U|βp|βα_↓|β1|4α=↓|44U|βp|4α+↓|4V|βp|4α_↓|4U|βp|βα
3351 +↓|β1|4|"o|4|→α_↓U|βp|βαα≤I1; |π∞ence |εU|βp|βα+↓|β1
3354 |πmod |εp|4α=↓|40. |πWhen |εU|βp|4|"o|4|→α+↓1,
3358 |πwe have |≥*/|βp|βα_↓|β1|4α=↓|44U|βp|4α_↓|4U|βp|βα+↓|β1|4α=↓
3360 |44U|βp|4α_↓|4V|βp|4α_↓|4U|βp|βα_↓|β1|4|"o|4|→α_↓U|βp|βα_↓|β
3360 1; |πhence |εU|βp|βα_↓|β1 |πmod |εp|4α=↓|40.
3365 |πWe have therefore proved that,λfor awl primes
3372 |ε≥, |πthere is an inte∧dj |ε|≤e(|1p) |πsuch
3379 that|'{A6}|ε*1|εUSujN)*2↓~↓*4≤e(≥)*3)*34←π.mdF44ε≥I4↓≡**45.]!|¬{V*2
3380 ≤((5∀*2(¬}V44¬}S45#[KJ(3)(;{**}["!|9*34←1←5416m∧qikf|ε*4n|[#usak
3380 xspofulivdsinoegdr, andnifn|εmN4α=↓|4m(N) |πis
3383 the smallest positive integer such that |εU|ur|)m(N)|)
3390 |πmod |εN|4α=↓|40, |πwe have|'{A6}|εU|βn|4|πmod|4|εN|4α=↓|40
3394 !!|πif and only if!!|εn |[7u a multiple of |εm(N).|J!(31)|;
3403 {A6}|π(This number |εm(N) |πis called the ``rank
3410 of apparition'' of |εN |πin the sequence.) To
3418 prove (31), observe that the sequence |εU|βm,
3425 U|βm|βα+↓|β1, U|βm|βα+↓|β2,|4.|4.|4. |πis congruent
3429 (modulo |εN) |πto |εaU|β0, aU|β1, aU|β2,|4.|4.|4.|4,
3435 |πwhere |εa|4α=↓|4U|βm|βα+↓|β1|4|πmod|4|εN |πis
3438 relatively prime to |εN |πbecause gcd(|εU|βn,|4U|βn|βα+↓|β1)
3443 |4α=↓|41.|'!|9|4|1|1|1←πWith these preliminaries
3447 out of the way, we are ready to prove Theorem
3457 L. By (21) and induction,|'{A6}|εL|βn|4α=↓|4V|β2|ln|4|πmod|4
3462 |ε(2|gq|4α_↓|41).←J!(32)|;↓A6}|πFurthermore,
3464 it follows from the identity |ε2U|βn|βα+↓|β1|4α=↓|44U|βn|4α+
3469 ↓|4V|βn |πthat gcd(|εU|βn,|4V|βn)|4|¬E|42, |πsince
3473 any common factor of |εU|βn |πand |εV|βn |πmust
3481 divide |εU|βn |πand |ε2U|βn|βα+↓|β1, |πwhile
3486 gcd(|εU|βn,|4U|βn|βα+↓|β1)|4α=↓|41. |πSo |εU|βn
3489 |πand |εV|βn |πhave no odd factor in common.
3497 Therefore if |εL|βq|βα_↓|β2|4α=↓|40 |πwe must
3502 have|'{A6}|εU|ur|)2|gq|gα_↓|Vg5(|4α=↓*34U|ur|)2|gq|gα_↓|g2|)V
3503 |ur|)2|gq|gα_↓|g2|)|4|∂|"o|40!(|πmodulo|4|ε2|gq|4α_↓|41),|;
3504 {A4}| U|ur|)2←gq|gα_↓|g2|)|4|L|=|↔6|"o|40!(|πmodulgN4←ε2|g¬S
3504 4α_↓|41).>{A6}Nπ'!|9|4|1←1|1]o∧ if |εmN4α≡↓←4m(↑6g¬|4α≠↓*441)
3507 |πis the rank of apparition of |ε2|gq|4α_↓|41,
3515 m |πmust be a divisor of |ε↑←gq|gα_↓*4g3∪|[~¬t
3522 noohu diviuxgcmfn|ε3]g¬|gα≠↓g2; |["hus |≥*2N4α*2↓426ε*3g¬Sv↓≤↓**
3525 g3#.|[↓wsqqplppvgv¬shhqwh|≥*2N4(*2466v¬|4α≤↓*441∞|[.kst
3526 thyjdfbre be prime: Let the factorcwawion off|εn
3533 |π~ds|ε∀|urdSβ1|)3|)|4.|4.←4.|4p|ure|βr|)r|).
3534 |πAll primes |εp|βj |πare greater than 3, since
3542 |εn |π∪s odd and congruefo to |ε(|→α≠↓1)←g¬|4α_↓|41|4α=↓|4|→
3548 α_↓2 (|πmodulo 3).λFrom (27)↔λ(3)↔,afff(3)↔wwskkm∧uhhaw
3552 |≥*/UβlH44["M45∞(([[mbkqgm|≥↓6V¬Q4↓↓45),|[↓qyjjs]≤{**}\εt|4α≡↓
3552 *444[∩vv((54≥≥IujjSi1↓≠↓↓4)4)((5∀Pi154~↓44*2≤))]4#[4.[4#]4,]4∀
3552 Iurje|r∧↓↓1|)⊃C)(|1p|βrN4α+↓|4|≤e|βr)*3≥2,|;{A6}|π*1and
3554 each |ε|≤e|βj |πis |→|¬N1. |ππhejefores|εε |π/usuumkwlpppaso
3559 xf|\*2M4*2466v¬Uv↓≤↓v3#.|[3wzh|≥*2Ni1→4*244≥7ukC)←¬DjF¬JjC)(5∀PU
3559 kjSij↓≤↓↓5(*2K)(*4≥≥PijK4α↓44*2≠SIj*2)?|π≤wshq¬ks|≥*2Ni1→44¬}S44≥
3559 7ukC)5¬JjK¬JjC)*45∀PukjSij↓≤↓↓4)*2K)(*2IijK4α↓44f5F↓75((55PIj*2(
3559 44(F**6F↓75))(Vgc..|[↓Wqx.,xbkkuuss |≥p|rj|6α"↓|4|≤e|βj
3561 |πis even, |εt|4|¬E|4n|β0/2|gr|gα_↓|g1, |πsincesasfactornof
3565 2λisslgfz eakm time the least common multiple
3572 ofstwo e¬en nuxbdjfsisstakef.,Cvmbuningchhesescjsuqls↔,qwshq
3574 ¬ks|ε)N¬Dz|¬E2(*4f↓6d37←))*4grcN¬W*/(F7d↓75))(VgvM44}}Q477);|[[
3574 yfcks|\≤c44}}SI66 [↓kff Qεh|6(≡|6m |πor |εt|4α=↓|42m,
3579 |πa power of 2. Therefore |εe|β1←4↓≡↓*3457,sSirC4457,|[↓kffik
3584 f|\*2n|[7usnmohpvcvxsqwsm¬uyhhq¬¬s I*2nI*2I66VvqIα≠|45|6α≡↓|4(2
3585 |gk|4α+↓|41)(2|gl|4α_↓|41) |πwhere |ε2|gk|4α+↓|41λ|πanff
3588 \↑|gl|4_↓|41 |πare prime. But the latter is obviokswysimposs
3595 u∧∧e when |εq |πis odd, so |εn |πis prime.|'|Ha*?*?{U0}{H10L12
folio 512 galley 13
3604 M29}|πW58320#Computer Programming!ch. 4!f. 512!g.
3608 13|'{A6}!|9|4|1|1|1Conversely, suppose that |εn|4α=↓|42|gq|4
3612 α_↓|41 |πis prime; we must show that |εV|ur|)2|gq|gα_↓|g2|)|
3619 4|"o|40 |π(modulo |εn). |πFor this purpose it
3626 su∃ces to prove that |εV|ur|)2|gq|gα_↓|g1|)|4|"o|4|→α_↓2
3631 (|πmodulo |εn), |πsince |εV|ur|)2|gq|gα_↓|g2|))|g2|4α_↓|42.
3635 |πNow|'{A2}|εV|ur|)2|gq|gα_↓|g1|)|4|∂α=↓|4|≥1(|¬H|v22|)|4α+↓
3636 |4|¬H|v26|)|1)/2|≥2|gn|gα+↓|g1|4α+↓|4|≥1(|¬H|v22|)|4α_↓|4|¬H
3636 |v26|)|1)/2|≥2|gn|gα+↓|g1|'{A3}|Lα=↓|42|gα_↓|gn|4|↔k|uc|)k|)
3637 |1|1|↔a|(n|4α+↓|41|d52k|)|↔s|¬H|v22|)|1|gn|gα+↓|g1|gα_↓|g2|g
3637 k|¬H|v26|)|1|g2|gk|4α=↓|42|g(|g1|gα_↓|gn|g)|g/|g2N4|↔k|uc|)k
3637 |)←1|1|↔a|(n|4α+↓|41|d52k|)|↔s|13|gk.>{A6}|πSince
3639 |εn |π/s prime,←'|ε|↔a|(n|4α+↓|41|d52k|)|↔s|4α=↓|4|↔a|(n|d52
3641 k|)|↔s|4α+↓|4|↔a|(n|d52k|4α_↓|41|)|↔s|;{A6}|πis
3643 divisible by |εn |πexcept when |εk|4α=↓|40 |πand
3650 |εk|4α=↓|4(n|4α+↓|41)/2; |πhence|'{A6}|ε2|ur(nα_↓1)/2←)|)V|u
3652 r|)2|gq|gα_↓|g1|)|4|"o|41|4α+↓|43|ur(nα+↓1)/2|)|)!(|πmodulo|
3652 4|εn).|;{A6}|πHere 2|4|"o|4(2|ur(|εqα+↓1)/2|)|))|g2,
3655 |πso 2|ur|ε(nα_↓1)/2|)|)|4←"o|4(2|ur(qα+↓1)/2|)|))|g(|gn|gα_
3656 ↓|g1|g)|4|"o|41 |πby Fermat's theorem. Finally,
3661 by a simple case of the law of quadratic reciprocity
3671 (exercise 1.2.4<47), |ε3|ur(nα_↓1)/2←)*4)|4←""N4←→α_↓1,
3674 |πsince |ε↔ |πmod 3|4α=↓|41 and |εn |πmod 4←4α=↓|43.
3682 This means |εV|ur|)2|gq|gα_↓|g1|)|4|"o|4|→α_↓2,
3685 |πso |εV|ur|)2|gq|gα_↓|g2|)|4|"oM45[['{A24∧|π|∨E|∨X|∨E|∨R|∨C
3686 |∨I|∨S|∨E|∨S|'{A12}{H9L11}|9|1|πN≡1|≡.|9|4|ε[|*/|↔O|↔c|\]|9|π
3687 If the sequence |εd|β0, d|β1, d|β2,|4.|4.|4.
3693 |πof trial divisors in Algorithm A contains a
3701 number which is not prime, why will it never
3710 appearcicnthe ouwput?|'{A3}|9|1|≡2|≡.|9|4|ε[|*/|↔O|↔C|\]|9|πI
3712 f it is known that the input |εN |πto Algorithm
3722 A is equal to 3 or more, could step A2 be eliminated?|'
3734 {A3}|9|1|≡3|≡.|9|4|ε[M|*/|↔P|↔c|\]|9|πShow that
3736 there is a number |εP |πwith the following property:
3745 If 1000|4|¬E|4n|4|¬E|41000000, then |εn |πis
3750 prime if and only if gcd(|εn,|4P)|4α=↓|41.|'{A3}|9|1|π|≡4|≡.
3756 |9|4|ε[M|*/|↔P|↔M|\]|9|π(J. M. Pollard.) Prove
3760 that (10) is the average value of the least |εn|4|¬R|41
3770 |πwith |εy|βn|4α*24y|β2|βn, |πif |εf |πis random
3776 modulo |εp.|'{A3}|9|1|≡5|≡.|9|4|ε[|*/|↔P|↔≡|\]|9←π*/se
3779 Fermat'↔smethod ton_nd thesfactorksof 10541 by
3784 hand.|'{A3}|9|1|≡6←≡.]9*34←ε[[|*/*3↔|↔MN\*4]9*3π4f
3786 |ε≥ |π/ssaf oddfprime and if |εN |π/ssnot a multiple
3795 of |εp,λ|π#covdsthaw thesnk¬xbjcmxfv¬wquss|≥*5→44¬DS4X44¬}Y4∀
3797 #,|[)ukv thqw |ε)Fg2]4≠↓**4]N4←""N4;Yv3/|[()mbkwgn|≥≥*2↔|[.qus
3799 uusbgqwponn|≥≥↔λ|π#ussquaw hon|ε(*41∀I4←¬FN45*2/2#],↓J↓Fπ'|:*35
3800 4≡6***2[::44≥[*/*/↔P↔**C\]::[αkukkusshhyspvgb∧wxxsmxfpvgggj¬mvcvv
3800 hhyssuu¬¬smxfUWgggclhmmFfmmnuux¬ckj¬ycvmvqqzjcqqyfnhhystw∧∧w
3800 ssfmgcussfxgcmmbkqqs |ε*2Miii|π-bmnoo exjctlys=εl
3803 an inoegral number of memory words.|'{A3}|9|1|≡8|≡.|9|4|ε[|*/
3809 |↔P|↔L|\]|9(The ``sieve offEratoszhefes↔''λ|π3⊃dfcdfourys{K9
3811 X|B)6.]|) Thesfollowing procedure evidefoly dkskovkjksuwlimb
3815 dfpvcvxsnk¬xbjkspwssshhqknuuvvv¬fnicmz∧∧jc|\],
3816 [(uccksiphcjxmv¬ssuwlphhysnmmvvcvxsnk¬xbjk;:sywjghqqphhuwlph
3816 hysmbdfnk¬xbjkspwssshhqkn \*2(; [πhyfnsukckssuv¬wqysygckksm¬q
3818 hhhysmvulppples |εp|=|rkNg2, p|βk(p|βk|4α+↓|42),
3821 p|βk(p|βk|4α+↓|44),|4.|4.|4. |πof the |εk|πth
3825 prime |εp|βk, |πfor |εk|4α=↓|42, 3, 4,|4.|4.|4.|4,
3831 |πuntil reaching a primds|εp|βk |πwith |εp|=|βkSg2|4|¬}|4N.
3837 |π*3yow ho∧sto ajjql thespcgcjdkjdsjksz ddskrcbddficoonan
3842 alggrithmnqqicm issdkrectlyssuitedfhone∃cient
3844 computer calculation,,usungnnonmultiplication.←'{A3}|9|1|≡9*3
3845 ≡.|9←4←ε[[|*/*3↔5|↔**C\**]9*3π1ez |ε↔ |π~bsuknmbdfnk¬xbj,|\*2N44}¬
3847 C477.|[(Ym∧qhhqwhikfhhysnk¬xbjc|≥\*2≤()) [πxfHHybgjxm7#7##7#↓
3848 Xiusuufkvvuxgcmxf Q*2n|9|1|≡9|≡.|9|4|ε[M|*/|↔P|↔C|\]|9|πLet
3850 |εn |πbe an odd number, |εn|4|¬R|43. |πShow that
3858 if the number |ε|≤l(n) |πof Theorem 3.2.1.2B
3865 is a divisor of |εn|4α_↓|41 |πbut not equal to
3874 |εn|4α_↓|41, |πthen |εn |πmust have the form
3881 |εp|β1p|β2|4.|4.|4.|4p|βt |πwhere the |εp'|πs
3885 are distinct primes and |εt|4|¬R|43.|'{A3}|≡1|≡0|≡.|9|4|ε[M|
3890 */|↔P|↔o|\]|9(|πJohn Selfridge.) Prove that if,
3895 for each prime divisor |εp |πof |εn|4α_↓|41,
3902 |πthere is a number |εx|βp |πsuch that |εx|ur(nα_↓1)/p|)p|)
3910 |πmod |εn|4|=|↔6α=↓|41 |πbut |εx|urnα_↓1|)p|)
3914 |πmod |εn|4α=↓|41, |πthen |εn |πis prime.|'{A3}|≡1|≡1|≡.|9|4
3920 |ε[M|*/|↔P|↔c|\]|9|πWhat outputs does Algorithm
3924 E give when |εN|4α=↓|4197209, |εk|4α=↓|45, m|4α=↓|41?
3930 [Hint|*/:|\ |¬H|v45|4|¬O|4197209|)|4α=↓|4992|4α+↓|4|"C|v41,|4
3931 495,|42,|4495,|41,|41984|)|"C.]|'{A3}|π|≡1|≡2|≡.|9|4|ε[M|*/|↔
3932 P|↔l|\]|9|πDesign an algorithm which uses the
3938 outputs of Algorithm E to _nd a proper factorization
3947 of |εN, |πif a solution to (17) can be found
3957 by combininvvhhe outputs of Algorithm E.|'{A3}|≡1|≡3|≡.|9|4|
3963 ε[M|*/|↔P|↔p|\]|9|πGiven a prime |εp |πand a positive
3970 integer |εd, |πwhat is the value of |εf(p,|4d),
3978 |πthe average number of times |εp |πdivides |εA|g2|4α_↓|4dB|
3985 g2, |πwhen |εA |πand |εB |πare random integers
3993 that are independent except for the condition
4000 gcd(A,|4B)|4α=↓|41?|'{A3}|≡1|≡4|≡.|9|4|ε[M|*/|↔P|↔c|\]|9|πPro
4001 ve that the number |εT |πin step E3 of Algorithm
4011 E will never be a multiple of an odd prime |εp
4022 |πfor which |ε(kN)|ur_↓1)/2|)|) |πmod |εp|4|¬Q|41.|'
4027 {A3}|π|≡1|≡5|≡.|9|4|ε[M|*/|↔L|↔M|\]|9(|πLucas
4028 and Lehmer.) Let |εP, Q |πbe relatively prime
4036 integers, and let |εU|β0|4α=↓|40, U|β1|4α=↓|41,
4041 U|βn|βα+↓|β1|4α=↓|4PU|βn|4α_↓|4QU|βn|βα_↓|β1
4042 |πfor |εn|4|¬R|41. |πProve that if |εN |πis a
4050 positive integer relatively prime to |ε2P|g2|4α_↓|48Q,
4056 |π_nd iff|εU|βNNβα~↓]β1 |π.od |εN|4α=↓|40, |πwhile
4061 |εU|ur|)(Nα+↓1)/p|) |πmod |εN|4|=|↔6α=↓|40 |πfor
4065 each prime |εp |πdividing |εN|4α+↓|41, |πthen
4071 |εN |πis prime. (Thpu gives a test for primality
4080 when the factors of |εN|4α+↓|41 |πare known instead
4088 of the factors of |εN|4α_↓|41. |πThe value of
4096 |εU|βm |πcan be evaluated in |εO(Nπgog|4|εm)
4102 |π↔zeps; cf. exercise 4.6.3<26.) [|εHint|*/:|\
4107 |πSee the proof of Theorem L.]|'{A3d|≡↓←≡6|≡.]9*34←ε[M|*/|↔C|↔
4113 c|\]|9*3π%je there in≠≡clewqsmkkxsMfjksfnfspvcvfs?*3,↓{↓x|≡14≡
4115 N≡.←9*344ε(MN*/←↔5|↔**C\*4,|π(7.,C.,Prjwt.)↔Ascomvlwzesprooxfoff
4115 pgcv¬wppyyxxshhyscvmv¬jkssoffFfjvjw"↔sHhebrjmntakkssthssfxgv
4115 nmxfuuhgjesqqmxssnobdsshq¬xshhysfxgvm|≥*2*2]4=*2),|[≤hejjs|≥≥
4116 |π≠kff|≥_u|π≠jjspgsutpvdsinme∧ejs sawiufyucvchhssfbglg∧unvnu
4117 jclhmdzpcccvnfkpionf:?(i)↔Ikf|ε(*2Sβ1,]4_|β1)↔]4.]4.N4.←4,,(q
4117 |βt,|4qSβt) |π_jesthe sons off|ε(q,|4a) |πthen
4122 |εq|4α=↓|4q|β1|4.|4.|4.|4q|βk|4α+↓|41. [|πIn
4124 particular if (|εq,|4a) |πhas no sons then |εq|4α=↓|42.]
4132 |π(ii) If |ε(r,|4b) |πis a son of |ε(q,|4a) |πthen
4141 |εa|ur(qα_↓1)/r|)|) |πmod |εq|4|=|↔6α=↓|41. |π(iii)
4145 For each node |ε(q,|4a), a|gq|gα_↓|g1 |πmod |εq|4α=↓|41.
4152 |πIt follows thaw |≥≥s|π/uspvcmesukff|ε_u|π/usuupvcmcppv¬sco
4155 oo modkwom|ε≥≡,|π↔brnawlinoddss|≥(q,]4_*2),[]π*4or
4157 example↔λthe tree proves that 1009 is prime.]
4164 Prove that such astree wuth rooo |ε(q,]4=*2↔|π.assuwhmofyh|≥*2
4170 (*2*2)|[[mbds↔,qqyjjs|≥*2f|[7usuucjwhyjcsqgowqyvggowcnvnfknctcm
4170 n.N'{A6}(1009,|411*2*4;*3'(2,|41)!(2,←41)!(2,|41)!(2,|41*2$(7,|4
4170 444444444444444444444444444444444444444444444444444444444444
4170 44444444*?(2,|41)!(2,|41)!(2,|41)!(2,|41)!(7,|43)!(3,|42)!(3,
4170 |42)|;|;{A33}{A6}|≡1|≡8|≡.|9|4|ε[HM|*/|↔P|↔O|\]|9|πGive
4173 a heuristic proof of (7), analogous to the text's
4182 derivation of (6). What is the approximate probability
4190 that |εp|βt|βα_↓|β1|4|¬E|4|¬H|v4p|βt|)|1?|'{A3}|π|≡1|≡9|≡.|9
4192 |4|ε[M|*/|↔P|↔C|\]|9|π(J. M. Pollard.) Show how
4197 to compute a number |εM |πwith the property that
4206 |ε|πgcd(|εM,|4N) |πis divisible by those primes
4212 |εp |πsuch that |εp|4α_↓|41 |πis a divisor of
4220 some given number |εD. [Hint|*/:|\ |πConsider
4226 numbers of the form |εa|gn|4α_↓|41.] |πExtend
4232 this to an e∃cient method which has high probability
4241 of discovering prime factors |εp |πof a given
4249 large number |εN, |πwhen all the prime power
4257 factors of |εp|4α_↓|41 |πare less than 10|g3
4264 except for at most one prime factor less than
4273 10|g5. [For example, the second-largest prime
4279 dividing (14) should be detected, since it is
4287 1|4α+↓|42|g4|4|¬O|45|g2|4|¬O|467|4|¬O|4107|4|¬O|4199|4|¬O|44
4287 1231.]|'{A3}|≡2|≡0|≡.|9|4|ε[M|*/|↔M|↔c|\]|9|πConsider
4289 exercise 19 with |εp|4α+↓|41 |πreplacing |εp|4α_↓|41.|'
4295 |Ha{U0}{H10L12M29}|πW58320#Computer Programming!ch.
folio 515 galley 14
4297 4!f. 515!g. 14|'*1|∨4|∨.|∨6|∨.|9|∨P|∨O|∨L|∨Y|∨N|∨O|∨M|∨I|∨A|∨
4300 L|4|4|∨A|∨R|∨I|∨T|∨H|∨M|∨E|∨T|∨I|∨C|'|'A |εpolynomial
4304 over S |πis an expression of the form|'{A6}|εu(x)|4α=↓|4u|βn
4312 x|gn|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4u|β1x|4α+↓|4u|β0,|J!(1)|;
4313 {A6}|πwhere the ``coe∃cients'' |εu|βn,|4.|4.|4.|4,|4u|β1,
4317 u|β0 |πare elements of some algebraic system
4324 |εS, |πand the ``variable'' |εx |πmay be regarded
4332 as a formal symbol with an indeterminate meaning.
4340 We will assume that the algebraic system |εS
4348 |πis a |εcommutative ring with identity|*/;|\
4354 |πthis means that |εS |πadmits the operations
4361 of addition, subtraction, and multiplication,
4366 satisfying the customary properties: Addition
4371 and multiplication are associative and commutative
4377 binary operations de_ned on |εS, |πwhere multiplication
4384 distributes over addition; and subtraction is
4390 the inverse of addition. There is an additive
4398 identity element 0 such that |εa|4α+↓|40|4α=↓|4a,
4404 |πandfa multiplicative identity element 1 such
4410 that |εa|4|¬O|41|4α=↓|4a, |πfor all |εa |πin
4416 |εS. |πThe polynomial |ε0x|gn|gα+↓|gm|4α+↓|4|¬O|4|¬O|4|¬O|4α
4419 +↓|40x|gn|gα+↓|g1|4α+↓|4u|βnx|gn|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4u
4419 |β1x|4α+↓|4u|β0 |πis regarded as the same polynomial
4426 as (1), altho¬¬vhits expression is formally di=erent.|'
4433 !|9|4|1|1|1We say that (1) is a polynomial of
4441 |εdegree n |πand |εleading coe∀cient u|βn |πif
4448 |εu|βn|4|=|↔6α=↓|40; |πand in this case we write|'
4455 {A6}deg|ε(u)|4α=↓|4n,]!|λ9(u)|4α=↓|4u|βn.|J!(2)|;
4456 {A6}|πBy convention, we also set|'{A6}|ε|πdeg(0)|4α=↓|4|→α_↓
4461 |¬X,!!|λ9(0)|4α=↓|40,|J!(3)|;{A6}|πwhere ``0''
4464 denotes the zero polynomial whose coe∃cients
4470 are all zero. We say |εu(x) |πis a |εmonic polynomial
4480 |πif |ε|λ9(u)|4α=↓|41.|'!|9|4|1|1|1|πArithmetic
4483 on polynomials consists primarily of addition,
4489 subtrjcoion, and muwtiplication; in some cases,
4495 further opejationsssukh ausfkvcsign,nexvonefoiazion,nfjkoorc
4497 ng, and takkng thesgreazest commonnfkvisor ujrsimportaft.
4503 The processes of addition, subtraction, and multiplication
4510 are de_ned in a natural way, as though the variable
4520 |εx |πwere an element of |εS: |πAddition and
4528 subtraction are done by adding or subtracting
4535 the coe∃cients of like powers of |εx. |πMultiplication
4543 is done by the rule|'{A6}|ε(u|βrx|gr|4α+↓|4|¬O|4|¬O|4|¬O|4α+
4548 ↓|4u|β0)(#|βsx|gs|4α+↓←4|¬O|4←¬O|4|¬O|4α+↓|4v|β0)|4α=↓|4(w|β
4548 r|βα+↓|βsx|gr|gα+↓|gs|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4w|β0),|;
4549 {A3}|πwhere|'|εw|βk|4α=↓|4u|β0v|βk|4α+↓|4u|β1v|βk|βα_↓|β1|4α
4550 +↓|4|¬O|4|¬O|4|¬O|4α+↓|4u|βk|βα_↓|β1v|β1|4α+↓|4u|βkv|β0.|J!(
4550 4)|;{A6}|πIn the latter formula |εu|βi |πor |εv|βj
4558 |πare treated as zeromicf Q=|4|¬QU4r |πor |εj|4|¬Q|4s.|'
4565 |π!|9|4|1|1|1The algebraic system |εS |πis usually
4571 the set of integers, or the rational numbers;
4579 or it may itself be a set of polynomials (in
4589 variables other than |εx); |πin the latter situation
4597 (1) is a |εmultivariate |πpolynomial, a polynomial
4604 in several variables. Another important case
4610 occurs when the algebraic system |εS |πconsists
4617 of the integers 0, 1,|4.|4.|4.|4, m|4α_↓|41,
4623 |πwith addition, subtraction, and multiplication
4628 performed mod|4|εm (|πcf. Eq. 4.3.2<11);?this
4633 is called |εpolynomiaw arithmetic modulo m.λ|π0he
4639 sqekiaw cjsesoffpogyfomcawiujcthmdzicnmodklo
4641 2,nwhen eakv offthescoe∃≡ceftssiis*?*?*?*?|πconsists
4644 of the integers 0, 1,|4.|4.|4.|4, m|4α_↓|41,
4650 |πwith addition, subtraction, and multiplication
4655 performed mod|4|εm (|πcf. Eq. 4.3.2<11); this
4661 is called |εpolynomial arithmetic modulo m. |πThe
4668 special case of polynomial arithmetic modulo
4674 2, when each of the coe∃cients is 0 or 1, is
4685 especially important.|'!|9|4|1|1|1The reader
4689 should note the similarity between polynomial
4695 arithmetic and multiple-precision arithmetic
4699 (Section 4.3.1), where the radix |εb |πis substituted
4707 for |εx. |πThe chief di=erence is that the coe∃cient
4716 |εu|βk |πof |εx|gk |πin polynomial arithmetic
4722 bears little or no essential relation to its
4730 neighboring coe∃cients |εu|βk|β|¬N|β1, |πso the
4735 idea of ``carrying'' from one place to the next
4744 is absent. In fact, polynomial arithmetic modulo
4751 |εb |πis essentially identical to multiple-precision
4757 arithmetic with radix |εb, |πexcept that all
4764 carries are suppressed. For example, compare
4770 the multiplication of (1101)|β2 by (1011)|β2
4776 in the binary number system with the analogous
4784 multiplication of |εx|g3|4α+↓|4x|g2|4α+↓|41 |πby
4788 |εx|g3|4α+↓|4x|4α+↓|41 |πmodulo 2:|'{A6}|∂!!!!!!!!!|∂!!!!!!!
4791 !!!!!|∂|ES;|>Binary system|;Polynomials modulo
4796 2|;>{A2}|>1101!!|9|?1101!!!!|?>|>α⊗↓|1|11011!!|9|?
4804 α⊗↓|1|11011!!!!|?>{A2}|>1101!!|9|?1101!!!!|?>
4810 |>1101|9|1!!|9|?1101|9|1!!!!|?>|>1101!|9|1|1|1!!|9|?
4816 1101!|9|1|1|1!!!!|?>{A2}|>10001111!!|9|?1111111!!!!|?
4821 >{A6}The product of these polynomials modulo
4828 2 is obtained by suppressing all carries, and
4836 it is |εx|g6|4α+↓|4x|g5|4α+↓|4x|g4|4α+↓|4x|g3|4α+↓|4x|g2|4α+
4838 ↓|4x|4α+↓|41. |πIf we had multiplied the same
4845 polynomials over the integers, without taking
4851 residues modulo 2, the result would have been
4859 |εx|g6|4α+↓|4x|g5|4α+↓|4x|g4|4α+↓|43x|g3|4α+↓|4x|g2|4α+↓|4x|
4859 4α+↓|41; |πagain carries are suppressed, but
4865 in this case the coe∃cients can get arbitrarily
4873 large.|'!|9|4|1|1|1In view of this strong analogy
4880 with multiple-precision arithmetic, it is unnecessary
4886 to discuss polynomial addition, subtraction,
4891 and multiplication much further in this section.
4898 However, we should point out some factors which
4906 often make polynomial arithmetic somewhat di=erent
4912 from multiple-precision arithmetic in practice:
4917 There is often a tendency to have a large number
4927 of zero coe∃cients, and polynomials of varying
4934 degrees, so special forms of representation are
4941 desirable; this situation is considered in Section
4948 2.2.4. Furthermore, arithmetic on polynomials
4953 in several variables leads to routines which
4960 are best understood in a recursive framework;
4967 this situation is discussed in Chapter 8.|'!|9|4|1|1|1Althou
4974 gh the techniques of polynomial addition, subtraction,
4981 and multiplication are comparatively straightforward,
4986 there are sevdrjlhmohyr impgggwnt asqacts oxnpolynomial
4992 arithmetic which ddssrve sqpdcial *?!|9|4|1|1|1Although
4997 the techniques of polynomial addition, subtraction,
5003 and multiplication are comparatively straightforward,
5008 there are several other important aspects of
5015 polynomial arithmetic which deserve special examination.
5021 The following subsections therefore discuss |εdivision
5027 |πof polynomials, with associated techniques
5032 such as _nding greatest common divisors; |εfactoring
5039 |πof polynomials; and also e∃cient |εevaluation
5045 |πof polynomials, i.e., _nding the value of |εu(x)
5053 |πwhen |εx |πis a given element of |εS, |πusing
5062 as few operations as possible. The special case
5070 of evalqating |εx|gn |πvery rapidly when |εn
5077 |πis large is quite important, so it is discussed
5086 in detail in Section 4.6.3.|'!|9|4|1|1|1The _rst
5093 major set of computer subroutines for doing polynomial
5101 arithmetic was the ALPAK system [W. S. Brown,
5109 J. P. Hyde, and B. A. Tague, |εBell System Technical
5119 Journal |π|≡4|≡2 (1963), 2081<2119; |π|≡4|≡3
5124 (1964), 785<804, 1547<1562]. Another earl*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
5128